Binary Search

Binary search gets taught as "the sorted-array trick," which undersells it badly. The actual idea is more general and more useful: any time a single comparison can reliably throw away half of everything you still need to check, you can search that space in O(log n) instead of O(n) — whether that space is array indices, a rotated array's structure, or (most powerfully) the space of *possible answers* to a question you haven't directly solved yet.

The invariant that makes it correct

Every binary search in this topic maintains the same shape: a range [lo, hi] that is guaranteed to still contain the answer, shrunk by roughly half on every iteration by discarding whichever side a single comparison proves can't contain it. Get the comparison wrong — or get the boundary update wrong (mid vs mid + 1 vs mid - 1) — and you either loop forever or silently discard the correct answer. This is why binary search has a reputation for being deceptively hard to get exactly right on the first try, even though the idea is simple.

Binary search doesn't require a sorted array — it requires a monotonic comparison

Find Peak Element is the clearest proof: the array isn't sorted at all, yet binary search still works, because the comparison nums[mid] < nums[mid + 1] reliably guarantees a peak exists on one particular side. That's the real requirement — not "is this sorted," but "does comparing the middle to something nearby let me provably eliminate half the space."

Binary search on the answer: the pattern that actually shows up in interviews

Koko Eating Bananas and Capacity To Ship Packages Within D Days look nothing like "search a sorted array" at first glance — there's no array to binary search *through*. The insight: the space of *possible answers* (every eating speed from 1 to max(piles), every capacity from max(weights) to sum(weights)) is itself monotonic — if speed k is fast enough to finish in time, every speed faster than k is too. That monotonicity is exactly the property binary search needs, so instead of testing every candidate answer one at a time (slow), you binary search the answer space directly, using a cheap feasibility check as the comparison.

// The shape every "binary search on the answer" problem shares:
long long lo = smallest_possible_answer;
long long hi = largest_possible_answer;
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (feasible(mid)) hi = mid;       // mid works -- a smaller answer might too
    else lo = mid + 1;                  // mid doesn't work -- need something bigger
}
// lo is now the SMALLEST value for which feasible() is true.
// feasible() itself is usually O(n) -- the win is doing O(log(range))
// feasibility checks instead of O(range) of them.

Common mistakes

• Mixing loop-condition styles — lo <= hi with hi = mid - 1/lo = mid + 1 is one consistent style; lo < hi with hi = mid/lo = mid + 1 is another. Both are correct on their own — mixing pieces from each is how infinite loops and off-by-ones happen.
• Integer overflow in mid = (lo + hi) / 2 — with large bounds, lo + hi can overflow before the division happens. mid = lo + (hi - lo) / 2 avoids it. Sqrt(x) has a second, sneakier version of this same bug: mid * mid overflows a 32-bit int long before x reaches INT_MAX, so the comparison itself needs a 64-bit type even though the inputs and answer both fit in int.
• Comparing against the wrong reference point in a rotated array — Find Minimum in Rotated Sorted Array needs nums[mid] compared against nums[hi] (the right edge), not nums[lo]; getting this backwards silently searches the wrong half.
• Turning a correct O(log n) shape back into O(n) accidentally — Find First and Last Position is the classic trap: find one occurrence with binary search, then linearly scan outward to find the edges of the run. That's O(n) again the moment a value repeats a lot. Two separate lower-bound searches keep it O(log n).