Binary Search, and the Search-on-Answer Pattern

Binary search is the cleanest possible demonstration of O(log n), and it's worth proving properly once — but this lesson's real destination is a less commonly taught application of the same idea: searching over a range of possible answers, for problems that don't look anything like "search a sorted array" on the surface.

Binary search, proved

function binarySearch(sortedArr, target) {
  let low = 0;
  let high = sortedArr.length - 1;
 
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
 
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) low = mid + 1;  // target must be to the right
    else high = mid - 1;                          // target must be to the left
  }
 
  return -1; // not found
}

Why this needs a sorted array, specifically: the entire algorithm rests on one guarantee. If sortedArr[mid] is smaller than the target, the target — if it exists at all — must be somewhere to the right, because sortedness guarantees everything to the left of mid is even smaller than sortedArr[mid] already was. That guarantee is what makes discarding an entire half of the array safe. On unsorted data, that guarantee is false — the target could be anywhere — and discarding a half could throw away the one place it actually was.

Complexity, proved the same way merge sort's recursion depth was proved several lessons ago: every comparison discards exactly half the remaining candidates. The number of times you can halve n before reaching a single candidate is log₂(n) — so binary search is O(log n), the same "repeated halving" argument, applied to narrowing a search range instead of splitting a sort's recursion.

The generalization: search on the space of answers

Here's the reframe that unlocks a whole category of problems: binary search's real requirement isn't "a sorted array" — it's a monotonic condition: as you move through the candidates in order, the answer to "does this candidate work" flips from false to true (or true to false) exactly once, never flip-flopping back and forth. A sorted array is one way to get that guarantee (values are ordered, so "is this element ≥ target" flips from false to true exactly once as you scan left to right) — but it's not the only way.

The problem: split a list of tasks across k workers, minimizing the maximum load any single worker gets assigned (a real load-balancing question — sharding work across web workers, say).

function canSplitWithMaxLoad(tasks, k, maxLoad) {
  let workersNeeded = 1;
  let currentLoad = 0;
 
  for (const task of tasks) {
    if (currentLoad + task > maxLoad) {
      workersNeeded++;
      currentLoad = task;
    } else {
      currentLoad += task;
    }
  }
 
  return workersNeeded <= k;
}
 
function minimizeMaxLoad(tasks, k) {
  let low = Math.max(...tasks);           // can't go below the single biggest task
  let high = tasks.reduce((a, b) => a + b, 0); // one worker taking everything
 
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (canSplitWithMaxLoad(tasks, k, mid)) {
      high = mid;       // mid works — try to do even better
    } else {
      low = mid + 1;    // mid doesn't work — need a bigger allowance
    }
  }
 
  return low;
}

There's no sorted array here at all — the thing being binary-searched is the candidate maximum load itself, ranging from "the single biggest task" (the floor — you can never go below what one task alone requires) to "the sum of everything" (one worker doing it all). The monotonic property that makes this valid: if a given maxLoad value is feasible (splits into k or fewer workers), every larger maxLoad is also feasible — feasibility never gets harder as the allowance grows. That's the exact same "everything on one side is uniformly one way, everything on the other side is uniformly the other" guarantee a sorted array gives, just expressed over a range of possible answers instead of array positions.

The complexity accounting that's easy to miss

The number of iterations is still O(log(range)) — same halving argument. But each iteration's canSplitWithMaxLoad check isn't free — it's an O(m) scan over the m tasks. The honest total complexity is O(log(range) * m), not simply O(log n). This is worth stating explicitly because it's a common oversight: "I used binary search, so it's O(log n)" skips the real cost of whatever work each iteration's feasibility check actually does — the same care this course has applied to every other pattern (two pointers, sliding window, tree traversal) applies here too.

What to remember

• Binary search requires sortedness specifically because it's what guarantees discarding half the array can never discard the target — and it achieves O(log n) by halving the remaining candidates every step.
• The search-on-answer pattern generalizes binary search from "a sorted array" to "any monotonic feasibility condition over a range of candidate answers" — useful for optimization-flavored problems that don't look like search at all on the surface.
• What makes search-on-answer valid is the same guarantee sortedness provides a normal binary search: feasibility (or the checked condition) must flip at most once as the candidate answer increases.
• The honest complexity of search-on-answer is O(log(range) × cost of one feasibility check) — don't drop the second factor just because the first one is a satisfying O(log n).