Binary Search as a Pattern — Search the Answer, Not the Array

Binary search finds values in sorted arrays — but as a pattern, it's bigger: any time you can ask a yes/no question that flips once across a range, you can binary search it.

The base template (bug-proof version)

function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Solidify it on the judge first: Binary Search (the hidden tests catch the classic off-by-ones — see the bug guide).

Level 2: rotated sorted array

Sorted array rotated at an unknown point. Key insight: at least one half is always still sorted. Check which half is sorted, check if the target lies in it, discard the other half. Still O(log n).

Level 3: binary search the ANSWER

The pattern interviews save for strong candidates. Example: "Ship packages within D days — find the minimum ship capacity."

// The answer (capacity) lives in a range [maxItem … totalWeight].
// For any capacity C we can CHECK feasibility in O(n): canShip(C)?
// Feasibility flips once: too small…too small…WORKS…works…works
// → binary search the range for the flip point!

let lo = maxItem, hi = totalWeight;
while (lo < hi) {
  const mid = (lo + hi) >> 1;
  if (canShip(mid)) hi = mid;     // works → try smaller
  else lo = mid + 1;              // fails → need bigger
}
return lo;

Spot it when…

• "Sorted" appears anywhere — array, rotated array, matrix with sorted rows.
• "Minimum X such that…" / "maximum X such that…" AND you can test a candidate X cheaply → search the answer space.
• O(log n) is demanded by the constraints (n up to 10⁹ → you can't even iterate).

The interview sentence: "Feasibility is monotonic here, so I'll binary search the answer." Saying monotonic signals you understand why it works.