Binary Search

1Introduction

This lecture explains binary search on an array sorted in nondecreasing order by means of a search-interval invariant. Linear search compares elements in sequence. Binary search instead uses the sorted order to exclude one part of the candidate interval with each comparison.

2Problem specification

Let $$A=(A_0,A_1,\dots ,A_{n-1})$$A=(A_0,A_1,\ldots,A_{n-1}) be an array of $$n\ge 0$$n\geq 0 elements satisfying

Thus, the array is sorted in nondecreasing order. Given a target $$x$$x, the algorithm returns an index $$i$$i satisfying $$A_i=x$$A_i=x if such an index exists, and otherwise reports absence.

Duplicate elements are allowed. If $$x$$x occurs at multiple indices, this algorithm may return any one of them; it does not promise the first or last occurrence.

3Half-open interval and midpoint

Represent the candidate indices by the half-open interval $$[l,r)$$[l,r). It contains $$l$$l but not $$r$$r, and its length is $$r-l$$r-l. When $$l<r$$l<r, define

Then $$l\le m<r$$l\leq m<r, so $$A_m$$A_m lies in the current candidate interval.

4Invariant

At the start of every iteration, maintain the following condition:

If $$x$$x occurs in the array, an index $$i$$i satisfying $$A_i=x$$A_i=x occurs in $$[l,r)$$[l,r).

4.1Initialization

Set $$l=0$$l=0 and $$r=n$$r=n. The candidate interval $$[0,n)$$[0,n) contains the entire array, so the invariant holds.

4.2Preservation

Under $$l<r$$l<r, compute the midpoint $$m$$m and compare $$A_m$$A_m with $$x$$x.

• If $$A_m=x$$A_m=x, return $$m$$m and terminate.
• If $$x<A_m$$x<A_m, sortedness gives $$A_i\ge A_m>x$$A_i\geq A_m>x for every $$i\in [m,r)$$i\in[m,r). Hence no matching index lies in $$[m,r)$$[m,r), and the update $$r=m$$r=m is valid.
• If $$A_m<x$$A_m<x, sortedness gives $$A_i\le A_m<x$$A_i\leq A_m<x for every $$i\in [l,m+1)$$i\in[l,m+1). Hence no matching index lies in $$[l,m+1)$$[l,m+1), and the update $$l=m+1$$l=m+1 is valid.

In either update, every index that can still match remains in the new candidate interval. The invariant is therefore preserved.

4.3Termination condition

When $$l=r$$l=r, the candidate interval is empty. If $$x$$x occurred in the array, the invariant would require a matching index in this empty interval, which is impossible. Thus $$x$$x is absent, and the algorithm may report absence.

5Termination

Let $$L=r-l>0$$L=r-l>0 be the interval length before an update. After $$r=m$$r=m, the new length is $$m-l$$m-l; after $$l=m+1$$l=m+1, it is $$r-m-1$$r-m-1. Since $$l\le m<r$$l\leq m<r, both cases satisfy $$0\le L^{\prime }<L$$0\leq L'<L.

Consequently, the nonnegative integer interval length decreases strictly at every iteration that does not terminate with a match. The algorithm must therefore terminate after finitely many iterations.

6Complexity

After one update, the new interval length satisfies

If $$n=0$$n=0, the loop performs no iterations. If $$n\ge 1$$n\geq1, then after $$k$$k updates its length is at most $$\lfloor n/2^k\rfloor$$\lfloor n/2^k\rfloor. Once $$2^k>n$$2^k>n, the interval is empty, so the algorithm performs at most $$\lfloor {\log }_{2}n\rfloor +1$$\lfloor\log_2 n\rfloor+1 iterations. Its time complexity is $$O\left(\log \right(n+1\left)\right)$$O(\log(n+1)), and its auxiliary-space complexity is $$O\left(1\right)$$O(1).

7Algorithm summary

1. Set $$[l,r)=[0,n)$$[l,r)=[0,n).
2. While $$l<r$$l<r, compute $$m=\lfloor (l+r)/2\rfloor$$m=\lfloor(l+r)/2\rfloor.
3. If $$A_m=x$$A_m=x, return $$m$$m. If $$x<A_m$$x<A_m, set $$r=m$$r=m; if $$A_m<x$$A_m<x, set $$l=m+1$$l=m+1.
4. If $$l=r$$l=r, report absence.

The correctness of binary search follows from candidate exclusion justified by sortedness, preservation of the invariant, and strict decrease of the interval length.