DAY 12 / 30 · WEEK 2

Binary Search

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

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)

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

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

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

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

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