DAY 13 / 30 · WEEK 2

Binary Search Variations

Goal of the day

• Find the first and last occurrence of a duplicated target — standard binary search only guarantees finding a match, not a specific one.
• Recognize "search on answer": binary search over a range of possible answers instead of over array indices, using a yes/no feasibility check at each guess.
• See two different loop shapes that both narrow toward a boundary instead of stopping at a match: first/last occurrence keeps Day 12's lo <= hi shape but changes what happens on a match, while search-on-answer switches to a lo < hi convergence loop entirely.

Concept

Day 12's template answers one question: "does this exact value exist, and if so, at which index?" Once you find a match, you stop. But two common situations need more:

Duplicates. If the target appears 4 times in a row, which index does standard binary search return? Whichever one mid happens to land on — not necessarily the first or last. To find a specific boundary, you don't stop at the first match: you record it as a candidate and keep narrowing in the same direction, discarding the match itself along with everything past it.

Search on answer. Some problems don't hand you a sorted array at all — they ask "what's the smallest/largest value that satisfies some condition?" (e.g. "the slowest eating speed that still finishes in time"). If that condition is monotonic — false for every value below some threshold, true for every value at or above it — you can binary search the space of possible answers, testing each guess with a feasibility check instead of an array comparison.

Diagram: first vs. last occurrence

Interactive visualization: find first and last occurrence

The code: first/last occurrence

function searchRange(nums, target) {
  function findBound(isFirst) {
    let lo = 0, hi = nums.length - 1, result = -1;
    while (lo <= hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (nums[mid] === target) {
        result = mid;                     // record this match...
        if (isFirst) hi = mid - 1;        // ...but keep looking further left
        else lo = mid + 1;                // ...or further right
      } else if (nums[mid] < target) lo = mid + 1;
      else hi = mid - 1;
    }
    return result;
  }
  return [findBound(true), findBound(false)];
}

Line by line:

• The only change from Day 12's template is the if (nums[mid] === target) branch: instead of return mid immediately, it saves mid as result and then keeps narrowing — toward lo for the first occurrence, toward hi for the last. Every other line is identical to Day 12.
• Calling the same function twice with a flag (isFirst) avoids duplicating the whole loop — the only difference between the two searches is which side keeps narrowing after a match.

Dry run: findBound(true) — first occurrence of 4 in [2, 4, 4, 4, 4, 7, 9]

The search keeps going even after finding a match at index 3 — that's the whole trick. The last confirmed match before the loop ends (index 1) is the true first occurrence.

Diagram: search on answer

Complexity

Interview corner

• Why does plain binary search fail to find "the first occurrence" reliably? It stops at the first match mid happens to land on, which depends on the exact sequence of midpoints computed — not on where the target actually starts. There is no general rule for which duplicate a plain search returns; treat it as arbitrary.
• How do you recognize a "search on answer" problem? Look for phrasing like "minimum/maximum value such that…" combined with a check that gets monotonically easier or harder to satisfy as the candidate value increases. If you can write a canDo(candidate) function that's false then true (or vice versa) as candidate increases, you can binary search candidate directly.
  ↳ Common follow-up: "What if higher isn't strictly better?" — then the condition isn't monotonic, and binary search doesn't apply at all; don't force it onto a non-monotonic problem.
• Why does findBound keep Day 12's lo <= hi shape, but Sqrt(x)/Koko switch to while (lo < hi)? Two different ways to reach a boundary. findBound still checks for an exact value match at each mid — same question as Day 12 — it just keeps going instead of returning immediately, so it keeps Day 12's inclusive loop shape and tracks the answer in a separate result variable. Sqrt(x)/Koko never check for an exact match at all — they converge lo and hi onto the same index, which needs the exclusive lo < hi loop so the loop stops the instant lo === hi, with no separate result variable needed.
  ⚠ Trap: mixing the two templates (e.g. while (lo < hi) with hi = mid - 1, or using lo = mid without the ceiling-mid fix from Day 12's trap diagram) is the single most common way this pattern breaks in an interview.

How to talk through it out loud: name which template you're using and why — "this needs the leftmost/rightmost boundary, so I'm using the narrowing template, not Day 12's exact-match one" — before writing a line of code. Interviewers are listening for whether you're pattern-matching the problem shape to the right template, not just typing something that happens to compile.

Practice problems

function mySqrt(x) {
  let lo = 0, hi = x;
  while (lo < hi) {
    const mid = lo + Math.ceil((hi - lo) / 2); // ceil, since lo = mid below
    if (mid * mid > x) hi = mid - 1;
    else lo = mid; // mid*mid <= x — keep mid as a candidate, don't exclude it
  }
  return lo;
}

function searchRange(nums, target) {
  function findBound(isFirst) {
    let lo = 0, hi = nums.length - 1, result = -1;
    while (lo <= hi) {
      const mid = lo + Math.floor((hi - lo) / 2);
      if (nums[mid] === target) {
        result = mid;
        if (isFirst) hi = mid - 1;
        else lo = mid + 1;
      } else if (nums[mid] < target) lo = mid + 1;
      else hi = mid - 1;
    }
    return result;
  }
  return [findBound(true), findBound(false)];
}

function minEatingSpeed(piles, h) {
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    const hours = piles.reduce((sum, p) => sum + Math.ceil(p / mid), 0);
    if (hours <= h) hi = mid;      // mid works — try slower (smaller) speeds
    else lo = mid + 1;             // mid too slow — need faster speeds
  }
  return lo;
}

Quiz