Binary Search

The idea

If you can look at the middle of a range and decide which half cannot contain the answer, you can throw that half away. Repeating this takes O(log n) steps: a billion items need only ~30 comparisons.

Binary search does not require a sorted array. It requires a monotonic predicate: a yes/no question whose answers look like

index:   0  1  2  3  4  5  6  7
pred:    F  F  F  F  T  T  T  T
                     ^ find this boundary

See it step by step in the binary search visualizer.

The one template to remember

Search for the first index where pred is true on the half-open range [lo, hi):

def first_true(lo, hi, pred):
    """Smallest x in [lo, hi) with pred(x) True, or hi if none.
    Requires pred to be F...F T...T on [lo, hi)."""
    while lo < hi:
        mid = (lo + hi) // 2
        if pred(mid):
            hi = mid          # mid might be the answer; keep it
        else:
            lo = mid + 1      # mid is definitely not the answer
    return lo

// smallest x in [lo, hi) with pred(x) true, or hi if none
template <class F>
long long firstTrue(long long lo, long long hi, F pred) {
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (pred(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Why this template is safe:

• The loop invariant: the answer is always in [lo, hi] (with hi meaning “none”).
• mid < hi always, so hi = mid shrinks the range; lo = mid + 1 shrinks it too. No infinite loops.
• When the loop ends lo == hi — no need to decide which one to return.

Everything else is a choice of predicate:

Library versions

from bisect import bisect_left, bisect_right
i = bisect_left(a, x)     # first index with a[i] >= x
j = bisect_right(a, x)    # first index with a[i] > x
count = j - i
# Python 3.10+: bisect_left(a, x, key=...) for custom keys

auto it = lower_bound(a.begin(), a.end(), x);   // first >= x
auto jt = upper_bound(a.begin(), a.end(), x);   // first > x
int i = it - a.begin();
bool found = it != a.end() && *it == x;
// on std::set / std::map use the member functions: s.lower_bound(x)  (O(log n))

The classic closed-interval version

You'll also see this form; it's fine for “find exact target”:

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

Rotated sorted arrays

After rotation, at least one half around mid is sorted. Decide which, check whether the target lies in it, and keep the right 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 sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                         # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[lo] <= nums[mid]) {
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

Minimum of a rotated array — the predicate is nums[i] <= nums[-1] (true exactly on the second sorted run, which starts at the minimum):

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        # min is strictly right of mid
        else:
            hi = mid            # min is mid or to the left
    return nums[lo]

With duplicates, when nums[mid] == nums[hi] you can only do hi -= 1 → worst case O(n).

Binary search on the answer

The most important and most disguised form. Instead of searching an array, search the range of possible answers.

Recipe:

1. Identify the answer's range [lo, hi] (e.g. [1, max(piles)]).
2. Write feasible(x) — often a greedy simulation.
3. Confirm monotonicity: if x works, does x + 1 work? (for “minimum”) or does x − 1 work? (for “maximum”).
4. Find the first feasible x.

Example: Koko eating bananas

def min_eating_speed(piles, h):
    def feasible(speed):
        return sum((p + speed - 1) // speed for p in piles) <= h
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

int minEatingSpeed(vector<int>& piles, int h) {
    auto feasible = [&](long long s) {
        long long hours = 0;
        for (int p : piles) hours += (p + s - 1) / s;
        return hours <= h;
    };
    long long lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid; else lo = mid + 1;
    }
    return lo;
}

Example: split array largest sum (minimize the maximum)

“Minimize the maximum” / “maximize the minimum” is the strongest hint for binary search on the answer.

def split_array(nums, k):
    def pieces_needed(cap):            # greedy: fill each piece as much as possible
        pieces, cur = 1, 0
        for x in nums:
            if cur + x > cap:
                pieces += 1
                cur = 0
            cur += x
        return pieces

    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if pieces_needed(mid) <= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

Maximizing instead of minimizing

For “the largest x such that feasible(x)”, the predicate is T…T F…F. Search for the first infeasible x and subtract 1, or flip the template with an upper mid:

def last_true(lo, hi, pred):       # largest x in [lo, hi] with pred(x), assumes pred(lo)
    while lo < hi:
        mid = (lo + hi + 1) // 2   # round UP, or lo = mid loops forever
        if pred(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

Examples: Magnetic Force Between Two Balls (maximize minimum distance), Maximum Candies Allocated to K Children.

Binary search on real numbers

Loop a fixed number of times (e.g. 100) instead of comparing floats:

lo, hi = 0.0, 1e9
for _ in range(100):
    mid = (lo + hi) / 2
    if feasible(mid):
        hi = mid
    else:
        lo = mid

Other forms

• Peak finding: compare nums[mid] with nums[mid + 1] and move toward the larger neighbour — a peak must exist on that side.
• 2D matrix sorted row-wise and column-wise: not binary search, but a staircase walk from the top-right corner in O(R + C).
• Answer is a k-th smallest value (k-th smallest in a sorted matrix, k-th pair distance): binary search the value v and count how many elements are ≤ v.
• Median of two sorted arrays: binary search the partition point of the smaller array. O(log min(m, n)).

Debugging checklist

1. Is the predicate really monotone over the whole range?
2. Are lo and hi wide enough to contain the answer (and the “none” case)?
3. Does every branch shrink the range? (lo = mid requires rounding mid up.)
4. Overflow in mid or in the feasibility sum (use 64-bit).
5. Test on arrays of size 0, 1, 2 and with the target at both ends.