Binary Search — Classic Search and "Binary Search on the Answer"

Binary search finds an item in a sorted array by checking the middle and throwing away half of the remaining range every step. A million elements need only about 20 comparisons — that's O(log n).

But the real interview power of binary search is broader: it works on any search space where the answer is monotonic — "if x works, every bigger x also works". That idea, binary search on the answer, solves many hard-looking problems.

The classic template

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2      # avoids overflow in Java/C++
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1               # target is in the right half
        else:
            hi = mid - 1               # target is in the left half
    return -1

int binarySearch(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1; else hi = mid - 1;
    }
    return -1;
}

Dry run — find 7 in [1, 3, 5, 7, 9, 11]:

lo	hi	mid	nums[mid]	action
0	5	2	5	5 < 7 → lo = 3
3	5	4	9	9 > 7 → hi = 3
3	3	3	7	found at 3

Why lo + (hi - lo) / 2 and not (lo + hi) / 2? In Java, lo + hi can overflow when both are near 2³¹. The first form never overflows.

Lower bound: the first position where something becomes true

Many problems need "the first index with nums[i] >= target" (insert position, first occurrence). Use a slightly different loop that keeps the answer inside [lo, hi]:

def lower_bound(nums, target):
    lo, hi = 0, len(nums)            # hi = len: "not found" means insert at the end
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1             # answer is to the right of mid
        else:
            hi = mid                 # mid might be the answer — keep it
    return lo

• Search Insert Position is exactly lower_bound.
• First and last position of x: first = lower_bound(x); last = lower_bound(x + 1) − 1 (check they're valid and actually equal x).

Python has this built in: bisect.bisect_left(nums, target).

Rotated sorted array

[4, 5, 6, 7, 0, 1, 2] is a sorted array rotated. At any mid, one half is still sorted. Check which half, and whether the target lies inside it:

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

Binary search on the answer

Koko Eating Bananas: piles [3, 6, 7, 11], h = 8 hours. Find the minimum eating speed k so Koko finishes in time.

Notice: if speed k works, any faster speed also works. The answers look like ✗ ✗ ✗ ✓ ✓ ✓ … — monotonic. So binary search over k from 1 to max(piles), and test each candidate with a quick check:

import math

def min_eating_speed(piles, h):
    def can_finish(k):
        return sum(math.ceil(p / k) for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_finish(mid):
            hi = mid          # mid works — try slower
        else:
            lo = mid + 1      # too slow — must go faster
    return lo

Time: O(n · log(max pile)). The same pattern solves Split Array Largest Sum, Capacity to Ship Packages, Minimum Days to Make Bouquets, Aggressive Cows and many more.

Recipe: 1) Is the answer a number in a range? 2) If x works, do all bigger (or smaller) values work? 3) Can you check a given x quickly? → Binary search on the answer.

How to recognise binary search

• The input is sorted (or sorted-then-rotated).
• The constraints are huge (n up to 10⁹) — you need O(log n).
• The question asks for the minimum / maximum value such that some condition holds.

Common mistakes

1. Infinite loops: using while lo < hi with lo = mid (never moves when hi = lo + 1). Pair lo < hi with lo = mid + 1 / hi = mid.
2. Off-by-one in the bounds: decide upfront whether hi is inclusive (len − 1) or exclusive (len) and stay consistent.
3. Overflow in (lo + hi) / 2 in Java/C++.
4. Using binary search on unsorted data.

Key takeaways

• Halving the range each step → O(log n).
• Know two templates: exact match (lo <= hi) and lower bound (lo < hi, hi = mid).
• Binary search on the answer works whenever "feasible" is monotonic — a top interview pattern.