Binary Search

Binary search is the payoff for having sorted data. Each comparison discards half of what remains, so a billion candidates collapse to about 30 questions.

The idea is easy. Getting the boundaries right is not — which is why it deserves its own section.

Two Templates

Nearly every binary search you write is one of these, and mixing lines between them is the source of almost every bug.

Template 1 — exact match (inclusive bounds)

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

Use it when you want to find a specific value. See Binary Search.

Template 2 — boundary / lower bound (exclusive upper bound)

lo = 0, hi = n            ← note: n, not n - 1
while lo < hi:            ← note: <, not <=
    mid = lo + (hi - lo) // 2
    if predicate(mid): hi = mid       ← KEEP mid, it may be the answer
    else:              lo = mid + 1
return lo

Use it when you want the first position where something becomes true. See Search Insert Position and First Bad Version.

The Real Insight: Binary Search Without an Array

Template 2 does not need an array. It needs a monotonic predicate — one that is false, false, …, false, true, true, …, true over a range.

First Bad Version is the clearest example: there is no array, only version numbers and an API. The predicate "is this version bad?" is monotonic because every version after a bad one is also bad, and that is all binary search requires.

This unlocks a whole family of "binary search on the answer" problems: minimum capacity to ship packages in d days, smallest divisor under a threshold, minimum eating speed. In each, you binary-search the answer space and use a feasibility check as the predicate.

The Three Classic Bugs

All Problems

Related Elsewhere

• H-Index — the pre-sorted variant is a binary search
• Is Subsequence — binary search over position lists in the follow-up
• Merge Sorted Array — another algorithm that exists only because the input is sorted