Binary Search

Reach for it when

• Sorted (or rotated sorted) input with an O(log n) requirement
• Minimize the maximum / maximize the minimum
• A yes/no predicate that flips exactly once as the answer grows

Core idea

Find the first index where a monotonic predicate becomes true. Keep the invariant that the answer is inside [lo, hi]; test mid and drop the half that cannot contain it. 'Binary search on the answer' applies the same loop to a range of candidate answers instead of array indices.

Template · O(log n) iterations times the cost of the predicate

def first_true(lo, hi, ok):   # ok is False...False True...True
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid                 # mid might be the answer
        else:
            lo = mid + 1             # answer is strictly right
    return lo

// ok(x) is false...false true...true on [lo, hi]
long long firstTrue(long long lo, long long hi, const function<bool(long long)>& ok) {
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;  // no overflow
        if (ok(mid)) hi = mid;               // mid might be the answer
        else lo = mid + 1;                   // answer is strictly right
    }
    return lo;
}

Common pitfalls

• lo = mid with mid = (lo + hi) // 2 loops forever: round up or use mid + 1
• Mixing closed [lo, hi] and half-open [lo, hi) conventions
• Check that the predicate really is monotonic

Practice · 0 / 13 done

• Binary SearchEasy
• Find First and Last Position of Element in Sorted ArrayMedium
• Find Minimum In Rotated Sorted ArrayMedium
• Koko Eating BananasMedium
• Search a 2D MatrixMedium
• Search In Rotated Sorted ArrayMedium
• Search Suggestions SystemMedium
• Single Element in a Sorted ArrayMedium
• Snapshot ArrayMedium
• Time Based Key Value StoreMedium
• Median of Two Sorted ArraysHard
• Partition Array Into Two Arrays to Minimize Sum DifferenceHard
• Split Array Largest SumHard