Chapter 9 — Binary Search

Binary search is not about arrays. It's about eliminating half the remaining possibilities with every decision.

Part 1: The Observation That Makes Binary Search Possible

Linear search on an unsorted array: you check element 0, then 1, then 2... O(n) worst case. No way around it — you might need to inspect every element.

Now sort the array. Check the middle element. Three outcomes:

1. arr[mid] === target → found.
2. arr[mid] < target → target, if it exists, is in the right half. Discard left half entirely.
3. arr[mid] > target → target, if it exists, is in the left half. Discard right half entirely.

Each comparison halves the remaining search space. After k comparisons: n / 2^k elements remain. When n / 2^k = 1, we're done. That happens when k = log₂(n). So: O(log n).

Two requirements for binary search:

1. Sorted (or structured) data — so that comparing the midpoint tells you which half to discard.
2. O(1) access by index — so you can jump to the midpoint instantly.

Arrays satisfy both. Linked lists fail requirement 2 (O(n) to reach the middle). This is why you can't binary search a linked list.

Part 2: The Physical Reality — What mid Is

Array: [1, 3, 5, 7, 9, 11, 13, 15]
Index:   0  1  2  3  4   5   6   7

Left pointer: left = 0. Right pointer: right = 7. (Inclusive on both ends.)

mid = Math.floor((left + right) / 2) = Math.floor(7/2) = 3
arr[3] = 7

If target = 9: 7 < 9 → search right half. left = mid + 1 = 4.

left=4, right=7. mid = Math.floor(11/2) = 5.
arr[5] = 11.
11 > 9 → search left half. right = mid - 1 = 4.

left=4, right=4. mid=4.
arr[4] = 9 === 9 → found at index 4. ✓

Three comparisons to find 9 in an 8-element array. Linear scan worst case: 5 comparisons (index 4). For n=1,000,000: binary search takes ≤ 20 comparisons. Linear scan takes up to 1,000,000. This is the O(log n) vs O(n) difference made concrete.

Part 3: The Template — and Why Off-By-One Errors Happen

There are three common binary search templates. Each has different loop termination conditions and pointer updates. Confusion between them is the single largest source of binary search bugs.

Template 1: Find Exact Match (Inclusive [left, right])

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

  while (left <= right) {               // ← <= because both ends are valid positions
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] === target) return mid;
    else if (nums[mid] < target) left = mid + 1;   // ← +1: mid is already checked
    else right = mid - 1;                           // ← -1: mid is already checked
  }

  return -1;  // not found
}

Loop invariant: Target, if it exists, is in the range [left, right]. Loop terminates when left > right — empty range.

Why left <= right not left < right? When left === right, there's still one unchecked element. Using < would skip it.

Why mid + 1 and mid - 1? mid is already compared. The next search range excludes it. Using mid instead of mid + 1 when nums[mid] < target would cause infinite loops when left === right (mid wouldn't advance).

Template 2: Find Leftmost Position (Half-open [left, right))

function lowerBound(nums, target) {
  let left = 0, right = nums.length;  // ← right is length, not length-1

  while (left < right) {              // ← < because right is exclusive
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] < target) left = mid + 1;
    else right = mid;                 // ← right = mid (not mid-1) because right is exclusive
  }

  return left;  // left === right: first index where nums[index] >= target
}

This finds the leftmost index where you could insert target to keep the array sorted (or the leftmost occurrence of target if it exists). Equivalent to JavaScript's Array.prototype.findIndex for sorted arrays, or Python's bisect_left.

Loop invariant: The answer is in [left, right). When left === right, we've converged.

Template 3: Find Rightmost Position

function upperBound(nums, target) {
  let left = 0, right = nums.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] <= target) left = mid + 1;   // ← <= so we go past equal elements
    else right = mid;
  }

  return left - 1;  // last index where nums[index] <= target
}

Which template to use:

• Looking for a specific value, return index or -1 → Template 1.
• "Find the first/leftmost position satisfying condition" → Template 2.
• "Find the last/rightmost position satisfying condition" → Template 3.

The integer overflow trap: Math.floor((left + right) / 2) can overflow if left + right > 2^31 - 1 in languages with 32-bit integers (Java, C++). The safe version: left + Math.floor((right - left) / 2). JavaScript uses 64-bit floats for all numbers, so overflow is not an issue, but write the safe version in interviews anyway — it signals awareness.

Part 4: Deriving the Complexity

Time: At each iteration, the search space halves. Starting with n elements:

Step 0: n elements
Step 1: n/2 elements
Step 2: n/4 elements
...
Step k: n/2^k elements

Loop terminates when n/2^k ≤ 1, i.e., k ≥ log₂(n). So at most ceil(log₂(n)) iterations. O(log n) time.

Space: Template 1 and 2 use only three variables (left, right, mid). O(1) space.

Recursive binary search (Chapter 4a) uses O(log n) space for the call stack. The iterative version is preferable for space.

Key intuition: log₂(1,000,000,000) ≈ 30. Binary search on a billion elements: at most 30 comparisons. This is why database indexes (B-trees) are so fast — even a massive index has O(log n) lookup depth.

Part 5: Binary Search on the Answer Space — The Key Insight

This is the upgrade that takes binary search from "find a value in a sorted array" to a general technique.

The generalized form:

If you have a predicate f(x) such that there exists some boundary k where f(x) is false for all x < k and true for all x ≥ k (monotonic), then you can binary search on x to find k in O(log(range)) time.

The "array" doesn't have to be an array. It's a search space — any ordered domain where the predicate transitions from false to true exactly once.

Example — Koko Eating Bananas:

Koko eats bananas at rate k bananas per hour. Can she finish all piles within h hours?

The predicate: canFinish(k) = "at rate k, can she finish in h hours?" This is monotonic — if she can finish at rate k, she can certainly finish at rate k+1. There's a minimum k where she can finish. Binary search on k.

Example — Capacity to Ship Packages:

Ship all packages within d days with minimum weight capacity. The predicate: canShip(capacity) = "can we ship all packages in d days with this capacity?" Monotonic — larger capacity = easier to ship. Binary search on capacity.

The template for "binary search on answer":

function findMinValid(lo, hi, canDo) {
  // Find the smallest x in [lo, hi] where canDo(x) is true.
  // Assumes: canDo is false for x < answer, true for x >= answer.
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (canDo(mid)) hi = mid;      // mid works, try smaller
    else lo = mid + 1;             // mid doesn't work, need larger
  }
  return lo;  // smallest x where canDo(x) is true
}

This single template solves a huge family of problems. Recognizing "I need the smallest value satisfying a condition" → binary search on answer → write the canDo predicate → done.

Part 6: Binary Search on Rotated Sorted Arrays

A sorted array that has been "rotated" has a break point: [4,5,6,7,0,1,2]. It's still partially sorted — one half is always fully sorted.

Key insight: When you compute mid, one of the two halves ([left, mid] or [mid, right]) is always fully sorted. You can determine which half by comparing nums[left] with nums[mid].

• If nums[left] <= nums[mid]: left half is sorted.
  • If target is in [nums[left], nums[mid]): search left half.
  • Else: search right half.
• If nums[left] > nums[mid]: right half is sorted.
  • If target is in (nums[mid], nums[right]]: search right half.
  • Else: search left half.

function searchRotated(nums, target) {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;

    if (nums[left] <= nums[mid]) {
      // Left half [left..mid] is sorted
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;  // target in sorted left half
      } else {
        left = mid + 1;   // target in right half
      }
    } else {
      // Right half [mid..right] is sorted
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;   // target in sorted right half
      } else {
        right = mid - 1;  // target in left half
      }
    }
  }

  return -1;
}

Dry run: searchRotated([4,5,6,7,0,1,2], target=0)

left=0, right=6. mid=3. nums[3]=7 ≠ 0.
nums[left]=4 <= nums[mid]=7 → left half [4,5,6,7] is sorted.
Is 0 in [4, 7)? 4 <= 0? No. → search right half. left=4.

left=4, right=6. mid=5. nums[5]=1 ≠ 0.
nums[left]=nums[4]=0 <= nums[mid]=nums[5]=1 → left half [0,1] sorted.
Is 0 in [0, 1)? 0 <= 0 < 1? Yes. → search left half. right=4.

left=4, right=4. mid=4. nums[4]=0 === 0. return 4. ✓

Part 7: Finding the Minimum in a Rotated Array

Problem: Find the minimum in a rotated sorted array (no duplicates).
findMin([3,4,5,1,2]) → 1

The minimum is at the rotation point — the only place where nums[i] > nums[i+1].

Key observation: If nums[mid] > nums[right], the minimum is in the right half (the rotation point is right of mid). Otherwise the minimum is in the left half (including mid).

function findMin(nums) {
  let left = 0, right = nums.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (nums[mid] > nums[right]) {
      left = mid + 1;   // min is in right half
    } else {
      right = mid;      // min is in left half (mid could be the min)
    }
  }

  return nums[left];  // left === right: the minimum
}

Dry run: findMin([3,4,5,1,2])

left=0, right=4. mid=2. nums[2]=5 > nums[4]=2. → left=3.
left=3, right=4. mid=3. nums[3]=1 <= nums[4]=2. → right=3.
left=3 === right=3. return nums[3]=1. ✓

Why compare mid to right (not left)? Because we're looking for the rotation point. If nums[mid] > nums[right], the array dips somewhere between mid and right — the minimum is there. If nums[mid] <= nums[right], the right half is monotonically increasing and doesn't contain the minimum (or mid is the minimum).

Part 8: Monotonic Predicate — The Unified View

Every binary search problem has an underlying monotonic predicate. Making it explicit makes the solution obvious.

Pattern:

1. Define the search space [lo, hi].
2. Write canDo(x) — the predicate that returns true for the answer and all values beyond it.
3. Verify monotonicity: once canDo(x) is true, canDo(x+1) must also be true.
4. Apply the template: find the smallest x where canDo(x) is true.

Applied to standard binary search:

Array: [1,3,5,7,9], target=5.

Predicate: f(i) = (nums[i] >= 5). This is false for i=0,1, true for i=2,3,4. Binary search finds i=2 (leftmost true). If nums[2] === 5, found it.

Applied to Koko Eating Bananas:

Piles: [3,6,7,11], h=8 hours.

Predicate: canFinish(k) = (total hours at rate k) <= h.

Total hours at rate k = sum of ceil(pile/k) for each pile.
canFinish(1): ceil(3)+ceil(6)+ceil(7)+ceil(11) = 3+6+7+11 = 27 > 8. False.
canFinish(4): ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4) = 1+2+2+3 = 8 <= 8. True.
canFinish(3): 1+2+3+4 = 10 > 8. False.

Binary search on k in [1, max(piles)]:

function minEatingSpeed(piles, h) {
  let lo = 1, hi = Math.max(...piles);

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

  return lo;
}

Dry run: minEatingSpeed([3,6,7,11], h=8)

lo=1, hi=11. mid=6. hours=ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6)=1+1+2+2=6 <=8. hi=6.
lo=1, hi=6. mid=3. hours=1+2+3+4=10 > 8. lo=4.
lo=4, hi=6. mid=5. hours=1+2+2+3=8 <=8. hi=5.
lo=4, hi=5. mid=4. hours=1+2+2+3=8 <=8. hi=4.
lo=4 === hi=4. return 4. ✓

Complexity: O(n log m) where n = number of piles, m = max pile size (the search space). Each predicate evaluation is O(n).

Part 9: Mental Model — Recognizing Binary Search Problems

Strong signals:

1. "Sorted array + find/search" → Standard binary search or variant.
2. "Find minimum/maximum value satisfying a condition" where the condition is monotonic → Binary search on answer.
3. "Minimise the maximum" or "maximise the minimum" → Almost always binary search on the answer.
4. The search space is ordered and large (days, speeds, capacities, days, weights) → Binary search the space, verify with a predicate.
5. O(log n) time hinted in the problem constraints → Binary search.

NOT binary search when:

1. The array is unsorted and sorting would change the problem.
2. The predicate is not monotonic — you can't say "if x works, x+1 works."
3. You need all occurrences — binary search finds one position; collecting all requires additional linear scan.

The key question to ask yourself: "If I try a value in the middle of my search space and it fails, can I definitively eliminate one half?" If yes, binary search. If not, you need a different approach.

Part 10: Real Systems

Database B-Tree Indexes:
B-trees are the data structure behind nearly every database index (PostgreSQL, MySQL InnoDB, SQLite). A B-tree is essentially binary search generalized to n-ary trees. Each node stores sorted keys — searching does binary search within each node, then follows a pointer to the child. The height is O(log_B n) where B is the branching factor (often 100+). For a table with 100 million rows: a B-tree of order 100 has height ≤ 4. Four disk reads to find any row. This is why indexes make queries fast and why WHERE id = ? on an indexed column is nearly instant.

git bisect:
If you know a commit introduced a bug, git bisect binary searches through your commit history. You mark commits as "good" or "bad." Git checks out the middle commit, you test it, mark it. Git halves the remaining range. For 1024 commits: at most 10 steps. The predicate: test() returns true (bad) or false (good). Pure binary search on the commit timeline.

ldconfig / man page index:
Unix commands that maintain sorted indexes of libraries and manual pages use binary search to locate entries. /etc/ld.so.cache is a sorted binary cache that ldconfig binary searches to locate shared libraries in O(log n).

Redis Sorted Sets (ZADD / ZRANGEBYSCORE):
Redis sorted sets are implemented as skip lists — a probabilistic data structure that achieves O(log n) search, insert, and delete. Skip lists are conceptually layered binary searches: each level is a faster "highway" over the level below, with half the nodes. Looking up a score in a skip list makes O(log n) comparisons, same asymptotic as binary search on a sorted array.

PostgreSQL Query Planner — Index Range Scans:
When your query has WHERE age BETWEEN 25 AND 35, PostgreSQL doesn't binary search for both 25 and 35 separately. It uses lowerBound(25) to find the first entry ≥ 25, and upperBound(35) to find the first entry > 35, then scans linearly between them. This is Template 2 and Template 3 applied to the B-tree.

npm / package resolution:
npm resolves semver ranges (e.g., ^1.2.3) by binary searching a sorted list of published versions for the highest compatible version. The semver package's maxSatisfying function uses binary search internally.

Part 11: Vocabulary Map

Part 12: 5 Practice Problems

1. Trace and Predict

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

Trace f([1,2,2,3,3,3,4], 3). What does it return? Now trace f([1,2,2,3,3,3,4], 5). What does it return, and what does that value mean? Is this Template 1, 2, or 3? What is the loop invariant?

2. Find the Waste

You need to find both the leftmost and rightmost occurrence of a target in a sorted array. Approach A: linear scan, O(n). Approach B: two binary searches (one for leftmost, one for rightmost), O(log n). For input [1,2,2,2,3,3,4] and target=2, trace both binary searches. Verify both return correct indices [1, 3].

3. Failure Analysis

function binarySearch(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left < right) {           // bug 1?
    const mid = (left + right) / 2; // bug 2?
    if (nums[mid] < target) left = mid + 1;
    else if (nums[mid] > target) right = mid - 1;
    else return mid;
  }
  return -1;
}

Find the two bugs. For bug 1: what input causes a failure? For bug 2: what language and input causes a failure (it's fine in JavaScript but catastrophic in Java/C++)? Write the fixed version.

4. Design Under Constraints

Design shipWithinDays(weights, days) (LeetCode 1011): find the minimum ship capacity to deliver all packages within days days. Packages must be shipped in order; a day's load cannot exceed capacity.

shipWithinDays([1,2,3,4,5,6,7,8,9,10], days=5) → 15

Define the search space bounds (lo and hi). Write the canShip(capacity) predicate. Prove the predicate is monotonic. Apply the template. Trace the first 3 binary search steps.

5. Reach Beyond

findKthSmallestInMatrix (LeetCode 378): given an n×n matrix where each row and column is sorted in ascending order, find the kth smallest element.

Binary search on the answer: lo = matrix[0][0], hi = matrix[n-1][n-1]. The predicate: countLessOrEqual(mid) counts how many elements ≤ mid. If count ≥ k, answer ≤ mid.

Write countLessOrEqual efficiently (hint: start from bottom-left corner, use the sorted structure to skip rows/columns in O(n) total). Then apply the binary search template. What is the total complexity?

Connect Forward

Chapter 10 — Trees. Binary Search Trees (BST) are the tree equivalent of binary search. In a BST, the left child is always smaller and the right child is always larger — every comparison at a node eliminates one subtree, giving O(log n) average search. The BST property is binary search embedded in tree structure.

Chapter 12 (Graphs) uses BFS (Chapter 7's queue) and DFS (Chapter 4/7's stack) but some graph problems on grids use binary search on the answer (e.g., binary search on distance + BFS to verify).

Chapter 13 (Dynamic Programming) often has binary search optimization for specific DP problems — Longest Increasing Subsequence can be computed in O(n log n) using a patience sorting technique that's essentially binary search.

Connect Backward

Chapter 4 (Recursion) presented recursive binary search — O(log n) time but O(log n) space. This chapter's iterative versions are O(1) space. The iterative version is always preferred unless the recursion is trivially shallow.

Chapter 3 (HashMaps) offers O(1) lookup but requires exact key match. Binary search offers O(log n) lookup but handles range queries, "find nearest," and "find all satisfying condition" naturally. Neither is universally better: use HashMap for exact match, binary search for sorted data with range queries.