RoadmapDay 17 / 80
DSAMonth 1 · Week 4

Day 17: Binary Search Patterns

Go beyond "find x in a sorted array" — recognize and solve the "search on the answer space" variant that shows up in most real binary search interview questions.

Mark this day complete

Study

Concepts

The invariant that must hold: a monotonic predicate

Binary search works on ANY search space where you can define a boolean predicate `isValid(mid)` that is monotonic — false for a while, then true for the rest (or vice versa). Classic sorted-array search is the special case where the predicate is `nums[mid] >= target`. This generalization is what unlocks "search on the answer" problems like "minimum days to ship packages" or "koko eating bananas", where the search space is a RANGE OF POSSIBLE ANSWERS, not the input array itself.

Off-by-one bugs are the #1 real-world failure mode. Fix the loop invariant explicitly: use `while (left <= right)` when searching for an exact value (and return -1 if not found), or `while (left < right)` when converging left/right to the same boundary value (common in "search on answer" problems).

See It

Visualizations

Visualization

Binary search for target=7 in a sorted array

Each step halves the remaining search space — O(log n).

0
1
2
3
4
5
6
1
3
5
7
9
11
13

Build It

Code Examples

Classic binary search — exact match

js
function binarySearch(sortedArr, target) {
  let left = 0;
  let right = sortedArr.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2); // avoids overflow
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return -1; // not found
}

Search on the answer: Koko Eating Bananas

js
// Koko must eat all 'piles' within 'hours' hours, choosing a constant
// speed k (bananas/hour). Find the MINIMUM valid k.
function minEatingSpeed(piles, hours) {
  const hoursNeeded = (speed) =>
    piles.reduce((total, pile) => total + Math.ceil(pile / speed), 0);

  let left = 1;                      // slowest possible speed
  let right = Math.max(...piles);    // fastest speed ever needed

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (hoursNeeded(mid) <= hours) {
      right = mid; // mid WORKS — try to go even slower
    } else {
      left = mid + 1; // mid too slow — need to go faster
    }
  }
  return left; // left === right: the minimum valid speed
}

console.log(minEatingSpeed([3, 6, 7, 11], 8)); // 4

Remember

Key Takeaways

  • Binary search needs a monotonic predicate over the search space — not necessarily a sorted array of the input.
  • "Search on the answer" problems binary-search over a RANGE OF POSSIBLE ANSWERS, checking feasibility at each mid.
  • while (left <= right) for exact-match search; while (left < right) for boundary-converging search — pick deliberately.
  • left + Math.floor((right-left)/2) avoids the (theoretical in JS, real in other languages) integer overflow of (left+right)/2.
  • Trigger words: "minimum/maximum X such that Y is possible", "find the boundary where a condition flips".

Do It

Practice

  1. 1Solve "Find First and Last Position of Element in Sorted Array" using two separate binary searches (leftmost, rightmost bound).
  2. 2Solve "Capacity To Ship Packages Within D Days" — it is structurally identical to Koko Eating Bananas.
  3. 3Implement binary search recursively, then explain the space-complexity tradeoff vs the iterative version (O(log n) stack frames vs O(1)).