Day 12: Binary Search

DAY 12 / 30 · WEEK 2

Goal of the day

• Implement the classic iterative binary search template on a sorted array.
• Understand exactly why lo <= hi and hi = mid - 1 are correct — and why the “close enough” versions (lo < hi, hi = mid) quietly break, sometimes in an infinite loop.
• See that binary search isn’t just “find x in a sorted array” — it works anywhere you can ask a yes/no question that flips exactly once across the search space.

Concept

Guess a number between 1 and 100. Instead of guessing 1, 2, 3, 4… (linear, up to 100 guesses), guess 50 first. Told “higher”? You just eliminated half the numbers in one guess. Guess the midpoint of what’s left, every time — each guess halves the remaining possibilities, so 100 numbers takes at most 7 guesses, not 100. That halving is where O(log n) comes from: it’s the number of times you can cut n in half before you’re left with one candidate.

The catch: this only works if the search space is sorted (or more precisely, monotonic — see the Interview Corner for what that really means). On an unsorted array, “higher” or “lower” tells you nothing about where to look next.

Diagram: narrowing lo / mid / hi

Interactive visualization: full binary search

Running example: search for 9 in [1, 3, 5, 7, 9, 11, 13]

Press Play or Step to begin.

Step 0 / 0

▶ Play⏭ Step⟲ Reset🔀 Shuffle

The code

function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {                             // "="  matters — see below
    const mid = lo + Math.floor((hi - lo) / 2);   // not (lo+hi)/2 — see below
    if (nums[mid] === target) return mid;
    else if (nums[mid] < target) lo = mid + 1;    // answer is to the right
    else hi = mid - 1;                            // answer is to the left
  }
  return -1; // not found
}

Line by line:

• while (lo <= hi) — the range [lo, hi] is treated as inclusive on both ends, so the loop must still run when exactly one candidate is left (lo === hi). Using < here would skip checking that last candidate entirely.
• mid = lo + Math.floor((hi - lo) / 2) — computes the same midpoint as Math.floor((lo + hi) / 2), but written this way to dodge integer overflow in languages with fixed-width integers (Java, C++). JS numbers don’t overflow the same way at these sizes, but writing it the safe way is a cheap habit that signals you know why it exists.
• hi = mid - 1 / lo = mid + 1 — both moves exclude mid from the next range, because mid was just checked and ruled out. Forgetting the -1/+1 (using hi = mid instead) keeps a already-checked index in play — usually just wasteful, but combined with while (lo < hi) it can infinite-loop (see the trap below).

Dry run: search([1, 3, 5, 7, 9, 11, 13], target=9)

lo	hi	mid	arr[mid]	Compare to 9	Action
0	6	3	7	7 < 9	lo = 4 (search right half)
4	6	5	11	11 > 9	hi = 4 (search left half)
4	4	4	9	9 === 9	return 4 — found

3 comparisons to search 7 elements — log₂(7) ≈ 2.8, rounded up to 3. Compare to a linear scan, which could take up to 7.

Diagram: the off-by-one trap that infinite-loops

Complexity

Approach	Time	Space	Why
Iterative	O(log n)	O(1)	Halves the search range each step — log₂n steps to reach 1 element. No extra memory beyond a few index variables.
Recursive	O(log n)	O(log n)	Same halving, but each recursive call adds a call-stack frame (Day 9) — log n frames deep before returning.

Interview corner

Why lo <= hi instead of lo < hi? The range [lo, hi] is inclusive — when lo === hi, there’s still one unchecked candidate. < would exit the loop right before checking it, silently returning “not found” on an array where the target is the very last candidate remaining.

↳ Common follow-up: “When would you use lo < hi?” — in “find the boundary” templates (first/last occurrence, search-on-answer, Day 13’s topic), where you deliberately narrow to a single answer index rather than an exact match-or-fail. The loop shape changes with the problem shape — memorizing one template and forcing every problem into it is the trap.

What does “the search space must be sorted” really mean? More precisely: there must be a boolean condition that’s false for a prefix of the space and true for the rest (or vice versa) — a single flip point. A literal sorted array is the simplest case, but today’s Find Peak Element runs binary search on data that isn’t sorted at all, because “is this side going up or down” still flips at most once per direction.

⚠ Trap: don’t say “binary search needs a sorted array” as an absolute rule — say “needs a monotonic predicate,” and be ready to show an example (like Find Peak Element) where the array itself isn’t sorted.

How would you find the first occurrence of a duplicated target? Standard binary search stops at the first match it happens to hit, which isn’t necessarily the first index. You’d keep searching left even after finding a match, recording it as a candidate and narrowing hi = mid - 1 instead of returning immediately. This is exactly Day 13’s topic.

How to talk through it out loud: State the invariant first — “at every point in the loop, if the target exists, it’s somewhere in [lo, hi]” — then justify each boundary update by showing it preserves that invariant. Naming the invariant explicitly is what separates “I memorized this template” from “I understand why this template is correct,” and it’s exactly what lets you adapt the template when a problem needs a different shape (like Day 13’s variants).

Practice problems

1. Binary Search (Easy — LeetCode)

Given a sorted array of integers and a target value, return its index, or -1 if it’s not present. This is today’s template, applied directly.

Hint

Write the loop invariant down before you code: “if target exists, it’s in [lo, hi].” Every line of the loop body should be justified by keeping that true.

Show solution

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

2. Search in Rotated Sorted Array (Medium — LeetCode)

A sorted array has been rotated at an unknown pivot (e.g. [4,5,6,7,0,1,2]). Find a target’s index in O(log n) time.

Hint

At every mid, at least one of the two halves ([lo, mid] or [mid, hi]) is guaranteed to be normally sorted, even though the whole array isn’t. Figure out which half is sorted first (compare nums[lo] to nums[mid]), then check whether the target falls inside that sorted half’s range to decide which side to keep.

Show solution

function search(nums, target) {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) { // left half [lo, mid] is normally sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else { // right half [mid, hi] is normally sorted instead
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

3. Find Peak Element (Medium — LeetCode)

Given an array where nums[-1] = nums[n] = -∞, find any index whose value is strictly greater than both neighbors. The array is not sorted — this is the clearest example of “binary search works on any monotonic yes/no question,” not just literal sorted arrays.

Hint

The flip point: if nums[mid] > nums[mid+1], you’re on a downslope — a peak exists somewhere at or before mid, so keep the left side including mid (hi = mid, not mid - 1 — mid itself could be the peak). Otherwise a peak exists after mid, so lo = mid + 1. This is the boundary-search shape from the trap diagram above — use while (lo < hi), never lo <= hi, here.

Show solution

function findPeakElement(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] > nums[mid + 1]) hi = mid;     // peak is at or before mid
    else lo = mid + 1;                            // peak is after mid
  }
  return lo; // lo === hi, pointing at a peak
}

Quiz

Quiz 1: Why does using while (lo < hi) break the exact-match binary search template from today?

It skips checking the last remaining candidate when lo === hi.

With lo < hi, the loop exits as soon as lo === hi without ever checking that final remaining candidate — a target sitting exactly there is missed.

Quiz 2: What is binary search’s time complexity, and why?

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

Each comparison eliminates half of the remaining candidates, so the number of comparisons needed is log base 2 of n.

Quiz 3: What’s the real requirement for binary search to work on a dataset?

A monotonic condition — false-then-true (or vice versa) with one flip point.

The real requirement is a monotonic predicate — a condition that’s false then true (or true then false) with a single flip point. A literal sorted array is the most common example, but Find Peak Element shows it isn’t the only one.

Quiz 4: What’s the space-complexity difference between recursive and iterative binary search?

Recursive uses O(log n) extra space for the call stack; iterative uses O(1).

Recursive binary search has the same O(log n) time as iterative, but each recursive call adds a call-stack frame, costing O(log n) extra space that the iterative version doesn’t need.

Quiz 5: In a “search on answer” template using while (lo < hi), what bug does writing lo = mid instead of lo = mid + 1 risk?

An infinite loop — lo can get stuck and never reach hi.

With lo < hi and mid rounding down (Math.floor), if a branch sets lo = mid instead of lo = mid + 1, lo and hi can stay stuck at adjacent values forever — the loop condition never becomes false.