Skip to main content

Binary Search and Its Invariant: Correctness as a Template

What This Concept Is​

Binary search reduces an ordered candidate interval. A lower bound returns the first index with value at least target, or n. Use a half-open interval [lo,hi) and maintain: all indices below lo contain smaller keys, all indices at or above hi contain keys at least target. Initially both excluded regions are empty.

lo, hi = 0, len(a)
while lo < hi:
    mid = (lo + hi) // 2
    if a[mid] < target:
        lo = mid + 1
    else:
        hi = mid
return lo

Each branch preserves the excluded-region facts by sortedness, and strictly decreases hi-lo. At termination lo=hi, so the boundary is identified.

Why It Matters Here​

Many production errors are boundary-contract errors: an arbitrary match is not a lower bound, and a present duplicate is not a unique position. The invariant also transfers to searching a monotone predicate without building a sorted array.

Concrete Examples​

For [1,2,2,2,4] and target 2, lower-bound intervals are [0,5), [0,2), [0,1), then [1,1). The upper bound finds the first value strictly greater than 2 and returns 4. Thus the equal range is [1,4) with multiplicity 3. For target 3 both boundaries equal 4; absence is an empty interval, not an error. For empty input both are zero with no indexed reads.

A first-true predicate search has the same structure if false values precede true values. The predicate's evaluation cost C is part of total time: O(C log n) under a constant-length search domain and appropriate boundary handling.

Common Confusion / Misconceptions​

O(log n) comparisons do not imply O(log n) time on a linked list. Random access is a precondition of the array cost model. Checking sortedness before every query takes linear time; validate once at a boundary or state sortedness as a caller obligation. In bounded integer languages, lo+(hi-lo)//2 can avoid midpoint addition overflow when the indices themselves fit the type.

How To Use It​

Choose half-open or inclusive intervals and use that convention consistently. For upper bound, discard through mid when a[mid] <= target; otherwise move hi to mid. Lab B performs two searches and checks at most 2*n.bit_length() indexed reads, with no slicing. Report indexing cost separately from comparison count.

Check Yourself​

  1. What does each excluded region guarantee?
  2. Why does lo=mid fail to guarantee progress?
  3. Why can absence return an index inside the array?
  4. What additional precondition makes a predicate searchable?

Mini Drill or Application​

Derive upper bound without copying code blindly. Check targets before all keys, after all keys, absent between keys, and equal to every key. Use a linear boundary oracle on short inputs. Transfer: for nonnegative task sizes and contiguous groups, prove that feasibility of a maximum group load is monotone before binary-searching that load. See P5 and P6.

Read This Only If Stuck​

Use CLRS, Skiena, or Sedgewick and Wayne for binary-search boundaries, loop invariants, and monotone predicates. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.