parikshan

Binary Search

The core idea

If you can ask a yes/no question about a position and the answers follow a monotone pattern (NN...NNYY...YY), you can find the boundary in O(log n) instead of O(n). The array does not have to be sorted. The answers have to be sorted.

That reframing is the entire skill. Binary search is not about finding a number in a sorted array; it is about finding the boundary of a monotone predicate.

When to reach for it

Trigger phrases:

  • "sorted array, find ..."
  • "find the smallest / largest x such that ..."
  • "minimise / maximise the answer subject to ..."
  • "first version that fails" / "last version that passes"
  • "you may guess; the system answers higher / lower"
  • input size suggests you need O(log n) per query

If the brute force is O(n) and the problem demands O(log n), or if you are asked to "search the answer space", reach for binary search.

How to approach

The template that does not lie:

lo, hi = low_bound, high_bound          # inclusive
while lo < hi:
    mid = (lo + hi) // 2                # left-biased
    if predicate(mid):
        hi = mid                        # mid might be the answer
    else:
        lo = mid + 1                    # mid definitely is not
return lo                                # the boundary

Three commitments:

  1. Pick whether predicate returns True on the answer or on its complement. Stick with it.
  2. Pick whether hi is inclusive or exclusive. Stick with it.
  3. Pick what to return at the end. The loop invariant tells you.

Real-world applications

  • Database indexes: B-tree lookups are repeated binary searches.
  • Version control bisect: git bisect is binary search over commit history.
  • Capacity planning: the smallest server count that holds the load is binary search on a predicate.
  • Auto-tuning: the largest batch size that fits in memory.
  • Game AI: binary searching the difficulty level a player can clear.

In the AI-integrated workspace

Binary-search bugs are the single most common silent-correctness bug in generated code. The four classics are: (1) mid = (lo + hi) // 2 overflowing in languages with bounded integers (not Python, but watch C++ and Java), (2) lo = mid causing infinite loops, (3) inclusive vs exclusive hi confused mid-function, (4) returning lo when the predicate was never true.

Two-step review: ask the agent to state the loop invariant in English, then check that the return statement matches. Without an invariant, the code is a guess.

For "binary search the answer" problems, the agent will often default to a linear scan because the search-the-answer framing is unfamiliar. When you see for x in range(0, max_possible): if feasible(x): return x, that is the cue to reach for binary search.

Problems in this cluster

Easy: binary-search, search-insert-position, first-bad-version, sqrt-x. Medium: find-min-in-rotated-sorted-array, search-in-rotated-sorted-array.

Start with binary-search. The deep article spells out the invariant in full.