Day 13: Binary Search Variations

DAY 13 / 30 · WEEK 2

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

current range [lo, hi] mid (checking now) match found, still narrowing eliminated confirmed boundary

Find first and last occurrence of 4 in [2, 4, 4, 4, 4, 7, 9]

Press Play or Step to begin.

Step 0 / 0

▶ PlayStep ⏭⟲ Reset🔀 Shuffle

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]

lo	hi	mid	arr[mid]	Action
0	6	3	4	match! result=3, keep looking left → hi=2
0	2	1	4	match! result=1, keep looking left → hi=0
0	0	0	2	2 < 4 → lo=1
1	0	—	—	lo > hi, loop ends → return 1

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

Variant	Time	Space	Why
First/last occurrence	O(log n)	O(1)	Two independent binary searches over the same n-element array — still logarithmic, just with a factor-of-2 constant.
Search on answer (e.g. Koko)	O(n log m)	O(1)	log m guesses over the answer range (m = largest possible answer), each guess costing O(n) to check feasibility across all n piles.

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

1. Sqrt(x) (Easy — LeetCode: Sqrt(x))

Given a non-negative integer x, return the largest integer whose square is ≤ x — without using Math.sqrt.

Hint

The answer space is 0 to x. The condition “candidate² ≤ x” is monotonic (true for small candidates, false for large ones) — binary search that condition directly. Watch out: if you write it with lo = mid (biasing toward keeping larger feasible values), you need the ceiling-mid fix from Day 12’s trap diagram to avoid an infinite loop.

Solution

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;
}

2. Find First and Last Position of Element in Sorted Array (Medium — LeetCode: Find First and Last Position of Element in Sorted Array)

Given a sorted array with duplicates, return the first and last index of a target value, or [-1, -1] if it’s not present. Today’s main template, applied directly.

Hint

Run the first-occurrence search and the last-occurrence search independently — don’t try to combine them into one pass, the narrowing direction after a match is opposite for each.

Solution

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)];
}

3. Koko Eating Bananas (Medium — LeetCode: Koko Eating Bananas)

Koko has piles of bananas and h hours. Eating at integer speed v bananas/hour, each pile takes ceil(pile / v) hours. Find the minimum speed that finishes all piles within h hours.

Hint

This is search on answer: the answer space is speeds 1 to max(piles). Write canFinish(speed) that sums ceil(pile / speed) across all piles and checks it’s ≤ h — that’s your monotonic feasibility check. Binary search the speed axis for the smallest speed where it returns true.

Solution

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

1. When a target appears multiple times, which index does plain binary search (Day 12’s template) return?

   • Whichever index mid happens to land on first — not reliably first or last
   • Always the first occurrence
   • Always the last occurrence
   • Answer: Whichever index mid happens to land on first — not reliably first or last

2. How does the first-occurrence search change Day 12’s template after finding a match?

   • It records the match and keeps narrowing left instead of returning immediately
   • It restarts the whole search from index 0
   • It stops immediately, same as Day 12
   • Answer: It records the match and keeps narrowing left instead of returning immediately

3. What property must a “search on answer” feasibility check have?

   • It must be monotonic — false-then-true (or vice versa) as the candidate increases
   • It must run in O(1) time
   • The array of piles must be sorted first
   • Answer: It must be monotonic — false-then-true (or vice versa) as the candidate increases

4. What’s the time complexity of Koko Eating Bananas’ search-on-answer solution?

   • O(n log m) — n piles checked at each of log m candidate speeds
   • O(log n) — same as a plain array binary search
   • O(n · m) — every speed from 1 to m is tried against every pile
   • Answer: O(n log m) — n piles checked at each of log m candidate speeds

5. In Sqrt(x)’s solution, why does mid use Math.ceil instead of the usual Math.floor?

   • Because the “feasible” branch sets lo = mid, so mid must round up to avoid freezing at lo
   • Because Math.ceil gives a more numerically precise midpoint
   • There’s no real difference — either would work identically
   • Answer: Because the “feasible” branch sets lo = mid, so mid must round up to avoid freezing at lo