Binary Search

At a glance

The instinct

Binary search is not really about sorted arrays; it is about a monotonic predicate - a yes/no question that is false for a prefix of candidates and true for everything after (FFFFTTTT). In a sorted array the question is "is a[i] >= target?". In Find Minimum in Rotated Sorted Array it is "is a[i] <= a[last]?". In Koko Eating Bananas the candidates are speeds and the question is "can she finish in h hours at this speed?". Once you can phrase the problem as FFFFTTTT, you find the first T in O(log n) checks.

Recognise it

Not this pattern if...

• The data is unsorted and you need one lookup - a hash set is O(1); sorting first costs O(n log n).
• The predicate is not monotonic (works at 5, fails at 6, works at 7) - binary search returns nonsense; think DP or greedy.
• You need the k-th largest of an unsorted array - quickselect or a heap is the natural fit.
• You must report every matching element - locate the boundary, then the rest is linear.

Memory hack

Analogy - the oven dial. You want the lowest oven temperature that bakes a cake within 30 minutes. Every temperature below some point fails and every temperature above it succeeds. You would never try 1°, 2°, 3°...; you try the middle of the dial, then the middle of the remaining half, and pin it down in a handful of bakes.

Say it out loud:

1. "My predicate is ___, and over [lo, hi] it is false then true."
2. "I want the first true: if mid is true I keep it (hi = mid), otherwise I drop it (lo = mid + 1)."
3. "The loop ends when lo == hi; I confirm hi started at a value that is definitely feasible, or check the result afterwards."

How it works

Keep a range that is guaranteed to contain the answer and shrink it by half each step, never discarding the answer itself. With the half-open convention [lo, hi), hi = n means "not found / insert at the end".

Lower bound of 7 in [1, 3, 5, 7, 7, 9]:

Searching on the answer is the same loop. The only differences are that lo..hi is a range of possible answers (speeds, capacities, days) and the predicate is a function you write, usually a greedy O(n) simulation.

Java template

import java.util.function.LongPredicate;

class BinarySearchTemplates {
    // First index in [0, n] with a[i] >= target (n if none).
    // Insert position = lowerBound; first occurrence = lowerBound if a[i] == target;
    // last occurrence = lowerBound(a, target + 1) - 1.
    static int lowerBound(int[] a, int target) {
        int lo = 0, hi = a.length;              // search space [lo, hi)
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;       // avoids int overflow of (lo + hi)
            if (a[mid] >= target) hi = mid;     // mid could be the answer: keep it
            else lo = mid + 1;                  // mid is too small: discard it
        }
        return lo;
    }

    // Binary search on the answer: smallest x in [lo, hi] with ok(x) true.
    // Needs ok to be monotonic (false...false true...true) and ok(hi) to be true.
    static long minFeasible(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (ok.test(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    // Mirror image: largest x in [lo, hi] with ok(x) true (true...true false...false).
    static long maxFeasible(long lo, long hi, LongPredicate ok) {
        while (lo < hi) {
            long mid = lo + (hi - lo + 1) / 2;  // round UP, otherwise lo = mid can loop forever
            if (ok.test(mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }

    // Example feasibility check (Koko Eating Bananas): finish all piles in h hours at speed k?
    // Usage: minFeasible(1, maxPile, k -> canFinish(piles, k, h))
    static boolean canFinish(int[] piles, long k, long h) {
        long hours = 0;
        for (int p : piles) hours += (p + k - 1) / k;   // ceiling division
        return hours <= h;
    }
}

Complexity

• Search in an array: O(log n) time, O(1) space for the iterative version.
• Search on the answer: O(log(hi - lo) × cost of the check) - for Koko that is O(n log maxPile).
• 2D matrix as 1D: O(log(m·n)), mapping mid to (mid / cols, mid % cols).
• Median of Two Sorted Arrays: O(log min(m, n)) by binary searching the partition point in the shorter array.

Variations

• Bounds on sorted data - lower/upper bound and exact match. Search Insert Position, Find First and Last Position of Element in Sorted Array.
• Rotated arrays - decide which half is sorted, then whether the target lies inside it. Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array.
• Slope / peak - compare mid with mid + 1. Find Peak Element; Find in Mountain Array finds the peak, then searches the ascending and descending sides separately.
• Search on the answer - minimise or maximise a parameter with a feasibility test. Koko Eating Bananas.
• Flattened 2D - one search over the virtual array. Search a 2D Matrix.
• Prefix sums + search - weighted sampling. Random Pick with Weight.
• Partition search - cut both arrays so the left halves together hold half the elements. Median of Two Sorted Arrays.

Common mistakes

• Mixing conventions: hi = n with while (lo <= hi), or hi = n - 1 with hi = mid. Pick inclusive or half-open and keep every line consistent.
• Bad answer bounds: starting Koko's speed at 0 (division by zero), or choosing an hi that is not actually feasible.
• Summing in int inside the feasibility check - hours, days and weights overflow quickly; use long.
• Applying the plain rotated-array logic to arrays with duplicates: when a[mid] == a[hi] you cannot tell which side is sorted, so shrink hi by one (worst case O(n)).
• Writing (lo + hi) / 2 with large indices or answer ranges; use lo + (hi - lo) / 2.

All practice problems

10 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.