Binary Search

Updated Nov 19, 2026 · 4 min read
On this page

    Binary search is not only "find x in a sorted array". The general version is: you have a yes/no question ok(x) whose answers go no, no, …, no, yes, yes, …, yes as x grows, and you want the first yes. Each step checks the middle and throws away half the range, so it takes O(log n) checks.

    Once you see it that way, one template covers every variant, and the only work left is writing ok.

    When to recognise it

    • Sorted input (or sorted by some key) and you need a position: first ≥ target, last ≤ target, insert position.
    • O(log n) is asked for, or n is huge (10⁹) and you cannot even loop over it.
    • "Minimum X such that …" / "maximum X such that …": smallest speed, smallest capacity, largest minimum distance. If a bigger X always works when a smaller one does, binary search on X itself. This is called searching the answer.
    • Rotated or otherwise partly sorted arrays, and peaks: one comparison still tells you which half to keep.

    How it works

    Eight cells F F F F T T T T with an arrow at the first T labeled answer: the boundary. Below: for a sorted array ok(i) is nums[i] >= target; for search the answer ok(speed) is finishes(speed).
    Eight cells F F F F T T T T with an arrow at the first T labeled answer: the boundary. Below: for a sorted array ok(i) is nums[i] >= target; for search the answer ok(speed) is finishes(speed).

    Keep a range [lo, hi] of candidates that have not been decided yet. Check mid. If ok(mid) is true, the answer is mid or something to its left, so set hi = mid − 1. Otherwise it is to the right, so set lo = mid + 1. When the range is empty, lo is the first true.

    Template

    def first_true(lo, hi, ok):
        """Smallest x in [lo, hi] with ok(x) True, given ok is False...False True...True.
        Returns hi + 1 if ok is never True. One template for arrays and for 'search the answer'."""
        while lo <= hi:
            mid = (lo + hi) // 2
            if ok(mid):
                hi = mid - 1      # mid works; look for something smaller
            else:
                lo = mid + 1
        return lo
    
    
    def lower_bound(nums, target):
        """First index whose value is >= target."""
        return first_true(0, len(nums) - 1, lambda i: nums[i] >= target)

    first_true returns hi + 1 when nothing is true, so lower_bound returns len(nums) when every value is smaller than the target, which is exactly the insert position. In Java or C++ write mid = lo + (hi − lo) / 2 to avoid overflow.

    Searching the answer

    Koko eats bananas at speed s and must finish all piles within h hours. Faster always works if slower works, so ok(s) = finishes(s) flips once. The range of candidate speeds is 1 … max(piles).

    import math
    
    def min_eating_speed(piles, hours):
        """Search on the answer: the smallest speed that finishes in time."""
        def finishes(speed):
            return sum(math.ceil(p / speed) for p in piles) <= hours
        return first_true(1, max(piles), finishes)
    Table for piles [3, 6, 7, 11] and 8 hours: lo, hi, mid, hours needed at mid, and the decision. Speeds 6 and 4 work, 3 does not; the loop stops with lo = 4.
    Table for piles [3, 6, 7, 11] and 8 hours: lo, hi, mid, hours needed at mid, and the decision. Speeds 6 and 4 work, 3 does not; the loop stops with lo = 4.

    Time O(n log M), where M is the largest pile: log M checks, each O(n).

    Variants in one line each

    • Last position ≤ target = first_true(x > target) − 1.
    • Rotated sorted array: compare nums[mid] with nums[hi] to tell which half is sorted, then check whether the target lies in that half.
    • Peak element: if nums[mid] < nums[mid + 1], a peak is to the right. That is ok(i) = nums[i] > nums[i + 1].
    • Real numbers (square root to 6 decimals): loop a fixed number of times instead of lo <= hi.

    Common bugs

    • Mixing loop styles. while lo <= hi goes with hi = mid − 1; while lo < hi goes with hi = mid. Mixing them loops forever or skips the answer. Pick one template and keep it.
    • ok that is not monotonic. If yes and no alternate, binary search returns nonsense. Check that a bigger x can never turn a yes into a no.
    • Wrong range for search-the-answer: the low end must be a valid candidate (speed 1, not 0) and the high end must surely work.
    • Integer division in ok: hours are ceil(p / s); in integer languages write (p + s − 1) / s.

    Say this in the interview

    • "The answer is monotonic: if speed s works, every faster speed works too. So I binary search for the smallest working speed. That's log(max) checks at O(n) each."
    • "I keep the invariant that everything left of lo is false and everything right of hi is true, so when they cross, lo is the first true."

    Problems for this pattern

    1. Binary Search: the plain version.
    2. Search in Rotated Sorted Array: decide which half is sorted.
    3. Find Minimum in Rotated Sorted Array: compare mid with the right end.
    4. Find First and Last Position of Element in Sorted Array: two boundaries.
    5. Find Peak Element: binary search on an unsorted array.
    6. Koko Eating Bananas: search the answer.
    7. Median of Two Sorted Arrays: binary search on a partition, the hard one.
    8. Time Based Key-Value Store: binary search for the last timestamp at or before the query.
    9. Random Pick with Weight: prefix sums, then binary search for a random target.

    Related

    Arrays and Strings · Binary Search Trees (the same halving, stored as a tree) · Big-O for Interviews · Pattern Recognition Cheat Sheet