Binary Search

Binary search finds something in a sorted collection in $O(\log n)$ by repeatedly discarding half. It is easy to understand and famously easy to get wrong: off-by-one errors, infinite loops and overflow have tripped up professionals. The way out is to use one template and understand why it is correct. The deeper skill, and the one interviews reward, is recognising that binary search applies far beyond sorted arrays: any time a yes/no question flips from "no" to "yes" at a single boundary, you can binary search on the answer.

1. When this pattern applies

• The input is sorted (or rotated sorted) and you search for a value, position or boundary.
• The problem asks for the minimum value satisfying a condition, or the maximum value that still satisfies it, and the condition is monotonic: once true, it stays true for larger values (or the reverse).
• The brute force is $O(n)$ or $O(n^2)$ and the data has some order that lets you rule out half the options per step.
• A statement like "find the smallest capacity, speed or time such that ..." almost always means binary search on the answer.

2. One template: find the first position where a condition is true

Instead of memorising separate versions, think of the search space as a row of values where a predicate ok(i) is False ... False True ... True. You want the first True. The loop keeps an invariant: the answer lies in [lo, hi].

def first_true(lo, hi, ok):
    """Smallest i in [lo, hi) with ok(i) True, or hi if none."""
    while lo < hi:
        mid = lo + (hi - lo) // 2        # avoids overflow in fixed-width integers
        if ok(mid):
            hi = mid                      # mid might be the answer: keep it
        else:
            lo = mid + 1                  # mid is too small: discard it
    return lo

# the first index whose value is at least 7 in a sorted list
a = [1, 3, 5, 7, 9, 11]
assert first_true(0, len(a), lambda i: a[i] >= 7) == 3
assert first_true(0, len(a), lambda i: a[i] >= 100) == 6      # none: returns len
assert first_true(0, len(a), lambda i: a[i] >= 0) == 0

Why it terminates: each iteration strictly shrinks [lo, hi). If ok(mid) then hi = mid < hi, otherwise lo = mid + 1 > lo. Why it is correct: hi is only ever set to a position that is True, and lo is only ever moved past positions that are False.

Almost every binary search is this template with a different ok.

3. Classic uses of the template

Exact search. Find the first index where a[i] >= target, then check it equals the target.

def search(nums, target):
    i = first_true(0, len(nums), lambda k: nums[k] >= target)
    return i if i < len(nums) and nums[i] == target else -1

assert search([-1, 0, 3, 5, 9, 12], 9) == 4
assert search([-1, 0, 3, 5, 9, 12], 2) == -1
assert search([], 1) == -1

Lower bound and upper bound. The first index with a[i] >= x is the lower bound, and the first index with a[i] > x is the upper bound. Their difference is the count of x.

def count_occurrences(nums, x):
    lo = first_true(0, len(nums), lambda i: nums[i] >= x)
    hi = first_true(0, len(nums), lambda i: nums[i] > x)
    return hi - lo

assert count_occurrences([1, 2, 2, 2, 3], 2) == 3
assert count_occurrences([1, 2, 3], 5) == 0

Search insert position is just the lower bound. Python's bisect_left and bisect_right implement lower and upper bound, and you can use them in interviews when the problem is not about implementing binary search itself.

import bisect
assert bisect.bisect_left([1, 3, 5, 6], 5) == 2
assert bisect.bisect_right([1, 3, 5, 6], 5) == 3
assert bisect.bisect_left([1, 3, 5, 6], 7) == 4

First and last position of a value are the lower bound and the upper bound minus one.

def search_range(nums, target):
    lo = first_true(0, len(nums), lambda i: nums[i] >= target)
    if lo == len(nums) or nums[lo] != target:
        return [-1, -1]
    hi = first_true(0, len(nums), lambda i: nums[i] > target) - 1
    return [lo, hi]

assert search_range([5, 7, 7, 8, 8, 10], 8) == [3, 4]
assert search_range([5, 7, 7, 8, 8, 10], 6) == [-1, -1]

4. Rotated sorted arrays

A sorted array rotated at some pivot, such as [4, 5, 6, 7, 0, 1, 2], is not fully sorted, but at least one half of any split is sorted. Use that to decide where to go.

Find the minimum (the pivot). Compare nums[mid] with nums[hi]: if the middle is larger than the last element, the minimum is to the right of the middle. Otherwise it is at the middle or to the left.

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1                 # the minimum is strictly to the right
        else:
            hi = mid                     # mid could be the minimum
    return nums[lo]

assert find_min([3, 4, 5, 1, 2]) == 1
assert find_min([4, 5, 6, 7, 0, 1, 2]) == 0
assert find_min([11, 13, 15, 17]) == 11
assert find_min([2]) == 2

Search in a rotated array. Decide which half is sorted, then check whether the target lies inside that half.

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:                    # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                        # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

assert search_rotated([4, 5, 6, 7, 0, 1, 2], 0) == 4
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 3) == -1
assert search_rotated([1], 1) == 0

With duplicates, the sorted half cannot always be determined (nums[lo] == nums[mid] == nums[hi]), and the worst case degrades to $O(n)$. Mention this follow-up.

5. Binary search on the answer

Here the search space is not an array of data but a range of possible answers, and ok(x) asks "is it feasible with value x?". Feasibility must be monotonic.

Koko eating bananas. Piles of bananas, $h$ hours. Find the smallest eating speed $k$ per hour so that all are eaten in time. If speed $k$ works, any larger speed works too, so feasibility is monotonic. Check feasibility by summing the hours needed.

def min_eating_speed(piles, h):
    def can_finish(speed):
        hours = sum((p + speed - 1) // speed for p in piles)    # ceil(p / speed)
        return hours <= h
    return first_true(1, max(piles) + 1, can_finish)

assert min_eating_speed([3, 6, 7, 11], 8) == 4
assert min_eating_speed([30, 11, 23, 4, 20], 5) == 30
assert min_eating_speed([30, 11, 23, 4, 20], 6) == 23

Time $O(n\log m)$ for $n$ piles and maximum pile $m$: $\log m$ feasibility checks, each $O(n)$.

Capacity to ship packages within $D$ days. Same shape: the search range is from the heaviest package (must fit at least one) to the total weight (ship everything in one day).

def ship_within_days(weights, days):
    def feasible(capacity):
        used, load = 1, 0
        for w in weights:
            if load + w > capacity:
                used += 1
                load = 0
            load += w
        return used <= days
    return first_true(max(weights), sum(weights) + 1, feasible)

assert ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5) == 15
assert ship_within_days([3, 2, 2, 4, 1, 4], 3) == 6
assert ship_within_days([1, 2, 3, 1, 1], 4) == 3

Integer square root. Find the largest $x$ with $x^2\le n$. That is the first $x$ where $x^2>n$, minus one.

def my_sqrt(n):
    return first_true(0, n + 2, lambda x: x * x > n) - 1

assert my_sqrt(8) == 2
assert my_sqrt(16) == 4
assert my_sqrt(0) == 0
assert my_sqrt(1) == 1

Recipe for "binary search on the answer":

1. Identify the quantity being minimised or maximised, and its lowest and highest possible values.
2. Write feasible(x) that checks whether x works, in $O(n)$ or so.
3. Convince yourself it is monotonic (if x works, so does anything larger, for a minimisation).
4. Run the template over the range. For a maximisation, search for the first infeasible value and subtract one, or flip the predicate.

6. Searching without a full array

Find a peak element. A peak is greater than its neighbours. Move toward the larger neighbour, since a peak must exist in that direction.

def find_peak(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1                 # a peak exists to the right (the slope rises)
        else:
            hi = mid                     # mid could be a peak, or one lies to the left
    return lo

nums = [1, 2, 1, 3, 5, 6, 4]
assert nums[find_peak(nums)] in (2, 6)
assert find_peak([1]) == 0
assert find_peak([3, 2, 1]) == 0

This works with no sorted order at all: the guarantee is that a decision at the midpoint rules out half. Look for that property.

Time-based key-value store. Store values with timestamps and return the value at the latest timestamp at or before a query time: binary search on a sorted list of timestamps with bisect.

import bisect
from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.times = defaultdict(list)      # key -> increasing timestamps
        self.values = defaultdict(list)

    def set(self, key, value, timestamp):
        self.times[key].append(timestamp)
        self.values[key].append(value)

    def get(self, key, timestamp):
        i = bisect.bisect_right(self.times[key], timestamp)    # first timestamp > query
        return self.values[key][i - 1] if i else ""

tm = TimeMap()
tm.set("love", "high", 10)
tm.set("love", "low", 20)
assert tm.get("love", 5) == ""
assert tm.get("love", 10) == "high"
assert tm.get("love", 15) == "high"
assert tm.get("love", 25) == "low"

7. Median of two sorted arrays (the hard one)

Find the median of two sorted arrays in $O(\log (\min (m,n)))$. The idea: partition both arrays so that the left parts together contain half of all elements and every element on the left is at most every element on the right. Binary search on how many elements to take from the shorter array.

def find_median_sorted_arrays(a, b):
    if len(a) > len(b):
        a, b = b, a                                   # binary search on the shorter array
    m, n = len(a), len(b)
    half = (m + n + 1) // 2
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2                            # elements taken from a
        j = half - i                                  # elements taken from b
        a_left = a[i - 1] if i > 0 else float("-inf")
        a_right = a[i] if i < m else float("inf")
        b_left = b[j - 1] if j > 0 else float("-inf")
        b_right = b[j] if j < n else float("inf")
        if a_left <= b_right and b_left <= a_right:   # a valid partition
            if (m + n) % 2:
                return max(a_left, b_left)
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        if a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1

assert find_median_sorted_arrays([1, 3], [2]) == 2
assert find_median_sorted_arrays([1, 2], [3, 4]) == 2.5
assert find_median_sorted_arrays([], [1]) == 1

Know the idea and be able to explain the partition invariant. Writing it from scratch under time pressure is a high bar, so the explanation matters more than perfect code.

8. Choosing the form

9. Common mistakes

• Infinite loop from lo = mid with mid rounding down. In the template, lo = mid + 1 and hi = mid guarantee progress.
• Wrong loop condition mixing lo < hi and lo <= hi between templates. Stick to one template per problem.
• Off-by-one on the boundaries. Decide whether the range is half-open [lo, hi) or closed [lo, hi] and stay consistent.
• Integer overflow in (lo + hi) // 2 in languages with fixed-width integers. Use lo + (hi - lo) // 2.
• A non-monotonic predicate. If feasibility is not monotonic, binary search gives wrong answers. Check the property.
• Forgetting that the answer may not exist (returning hi, or a value out of range). Check after the loop.
• Searching a list with in or index when the data is sorted. That is $O(n)$ where $O(\log n)$ is available.

10. Practice set

1. Binary search, search insert position, first bad version.
2. Find first and last position, count of an element in a sorted array.
3. Search in rotated sorted array (with and without duplicates), find minimum in rotated sorted array.
4. Koko eating bananas, capacity to ship packages, split array largest sum.
5. Sqrt($x$), pow($x$, $n$) by repeated squaring, valid perfect square.
6. Find peak element, find the duplicate number (binary search on value range).
7. Search a 2D matrix (sorted rows and columns).
8. Time-based key-value store.
9. Median of two sorted arrays.
10. Minimum time to complete trips (binary search on time).