Binary search

Binary search finds a target $x$ in a sorted array $A$ by inspecting the middle of the remaining candidate range. If the middle entry is smaller than $x$, every entry to its left is also too small; if larger, every entry to its right is too large. One comparison therefore rules out many entries. Equal entries are allowed; this version returns any matching index, without promising the first occurrence.

Use indices starting at zero and inclusive endpoints $L,R$. Initially $L=0$, $R=n-1$, where $n$ is the array length. While $L\le R$, chooseThe brackets denote the floor function. Compare $A_m$ with $x$: return $m$ on equality; set $L=m+1$ if $A_m<x$; otherwise set $R=m-1$. If $L>R$, report absence. The updates exclude the already inspected middle entry. This also handles an empty array, whose initial endpoints are $0,-1$. Sedgewick and Wayne specify a sorted array as input and return a matching index or $-1$ for absence.^[ref]

For a fully worked example, take the sorted arraySearch for $x=23$:

For $x=24$, the first two steps agree. Next $24>23$ retains only index $6$; inspecting $A_6=38$ sets $R=5$. Now $L=6>5=R$, so the answer is "absent" after four comparisons.

The loop invariant is: the array stays sorted, $0\le L\le R+1\le n$, and every index containing $x$ lies between $L$ and $R$. It holds initially. The sorted array property justifies each exclusion. Returning on equality gives a match; an empty candidate range implies absence. Crucially, this loop invariant allows $x$ to be absent from the beginning.

For a nonempty range of size $s=R-L+1$, an unsuccessful comparison leaves at most $\lfloor s/2\rfloor$ candidates. Thus sizes satisfy $s_k\le \lfloor n/2^k\rfloor$ after $k$ unsuccessful comparisons. This proves termination and, for $n\ge 1$, at most $\lfloor {\log }_{2}n\rfloor +1$ middle-entry comparisons. The final singleton still needs inspection: $n=1$ requires one comparison, not zero. For $n=15$, the bound is four. This is the halving argument behind logarithmic time complexity.^[ref]

A decision tree with $q$ binary tests has at most $2^q$ leaves. Distinguishing $n$ possible matching positions therefore requires $q\ge \lceil {\log }_{2}n\rceil$. This lower bound counts binary tests, whereas the bound above counts three-way comparisons.

In a nondecreasing array, the first position whose entry is at least $x$ is found by maintaining a half-open unresolved interval $[l,h)$. Entries before $l$ are smaller than $x$; entries from $h$ onward are at least $x$. Initially $l=c_0,h=c_1$. At midpoint $m$, replace $l$ by $m+1$ if $A[m]<x$, and otherwise replace $h$ by $m$. Monotonicity preserves the loop invariant, and $h-l$ decreases. On exit $l=h$ is the first qualifying position, or $c_1$ if no such entry exists. Repeated values and endpoint cuts require no additional case.

In a nonempty rotation of a strictly increasing array, keep an inclusive interval containing its minimum. Compare its midpoint with its right endpoint. If the midpoint is larger, the minimum lies strictly to the right of the midpoint; otherwise the midpoint-to-right segment is increasing and the minimum lies at or left of the midpoint. The interval at least halves until one index remains. The cyclic predecessor of this minimum holds the maximum, so both extrema are found with $O(\log n)$ comparisons. Distinctness makes the two-way comparison decisive.

Find both the lower-bound search boundary $i$ and the upper-bound search boundary $j$ of a key $x$ in a sorted array. Every entry in $[i,j)$ is at least and at most $x$, so all are equal to $x$. Values immediately outside this interval, when present, are strictly smaller or strictly larger; the interval is consequently maximal. An absent key gives $i=j$ at its insertion position. Two binary searches give total time complexity $O(\log (N+1))$ under constant-cost comparison and indexed access.

For a sorted array $a[\mathrm{0..}N)$, find the unique boundary $p\in [0,N]$ with $a[\mathrm{0..}p)\le x<a[p..N)$. A binary search maintains $0\le l\le r\le N$, an excluded prefix $a[\mathrm{0..}l)\le x$, and an excluded suffix $x<a[r..N)$. At an interior midpoint $m$, replace $l$ by $m+1$ when $a(m)\le x$, and otherwise replace $r$ by $m$. Sortedness preserves the loop invariant; the width $r-l$ is a decreasing loop variant. Termination at $l=r$ gives the boundary, including $p=0$ and $p=N$. The time complexity is $O(\log (N+1))$ with constant-cost comparisons and indexed access. Unlike searching for $x+1$, this formulation does not risk integer overflow at the largest representable key.

Suppose a candidate integer interval contains $W$ possible values and an active array segment contains exactly all occurrences from that interval, with $m<W$ entries. The pigeonhole principle guarantees a missing value. Split the value interval into widths $W_L,W_R$ and use array partitioning to obtain occurrence counts $m_L,m_R$. If $m_L<W_L$, retain the left side. Otherwise $m_R=m-m_L<W-W_L=W_R$, so retain the right side. This works with duplicate entries because it needs only the inequality between occurrences and possible values.

Balancing the value widths gives $W_{i+1}\le \lceil W_i/2\rceil$, while the active scan length remains less than $W_i$. The total work is bounded by a geometric series and logarithmic loop overhead, hence $O(W_0)$ time complexity. On reaching width one, the retained occurrence count is zero, proving that the sole candidate is absent globally. This is a binary search over deficient value intervals, with local in-place array partitioning, rather than repeated full-array scans.

For $n=2^k-1$ distinct keys and a uniformly chosen present target, early-return binary search takes mean $k-1+k/n$ iterations. There are $2^d$ targets needing $d+1$ probes, so sum $(d+1)2^d$ over depths zero through $k-1$ and divide by $n$. A boundary search that always closes the interval takes exactly $k$ iterations. Their expected difference is $1-k/n<1$, even though an individual shallow target can save many probes.

For a nonincreasing array, maintain indices $0\le a\le b\le n$ such that entries before $a$ exceed the target and entries from $b$ onward are at most the target. Probe the middle of the half-open interval. A value above the target advances $a$ past that index; otherwise set $b$ to that index. The interval length decreases geometrically. At termination the common boundary is the first possible match, so one guarded equality test decides presence even with duplicates.

Suppose integer endpoints satisfy $l<r$ and $f(l)\le 0<f(r)$. Repeatedly test an interior midpoint and replace the endpoint with its matching sign. The loop invariant is the ordered opposite-sign bracket. The positive integer width is a loop variant, and at termination $r=l+1$. Thus an adjacent sign transition can be located in $O(\log (r-l))$ evaluations without assuming that $f$ is monotone. If $f$ extends continuously between the endpoints, the intermediate value theorem associates the sign bracket with a zero. This is different from finding the first true position of a globally monotone predicate.

For each candidate first index $i$ in a sorted array, use lower-bound search for $t-a(i)$ only in the suffix starting at $i+1$. A matching result is automatically at a different position. The outer loop invariant excludes all solutions whose smaller index precedes $i$; an unsuccessful suffix search extends this exclusion by one. Exhaustion proves absence of any pair. Searching all suffixes gives $O(N\log (N+1))$ running time and constant auxiliary space. Compute the complement in a sufficiently wide type to avoid integer overflow before comparison.

For a nondecreasing sorted array $a[\mathrm{0..}N)$ and target $x$, find the unique position $p\in [0,N]$ such that every earlier value is below $x$ and every later value is at least $x$. Equivalently, $p=\min (\{i\in [0,N):a(i)\ge x\}\cup \{N\})$. Uniqueness follows because, if $p<q$ both satisfied the partition, $a(p)$ would have to be both at least $x$ and below $x$. A half-open search interval maintains an excluded prefix of smaller values and an excluded suffix of greater-or-equal values. Allowing the sentinel $N$ handles an empty array or a target beyond its last entry.