Chapter 9a — Binary Search Problem Patterns

Every binary search problem is the same question: "What am I eliminating with each comparison, and why is that safe?"

Pattern Map

Problem Type	Search Space	Predicate	Template
Find value in sorted array	Indices	`arr[mid] == target`	Template 1 (exact match)
Count of target / range [first, last]	Indices	`arr[mid] >= target`	Template 2 + Template 3
Rotated array search	Indices	Compare halves for sorted side	Template 1 with branching
Find minimum in rotated	Indices	`arr[mid] > arr[right]`	Template 2
Minimise max / maximise min	Answer values	`canDo(mid)` predicate	Template 2 on answer space
2D matrix search	Row index then column	Row-level binary search	Nested Template 1
K-th smallest in sorted structure	Answer values	`countLessOrEqual(mid) >= k`	Template 2 on answer space

Problem 1: Binary Search (Basic)

Problem: Return the index of target in a sorted array, or -1.
search([-1,0,3,5,9,12], target=9) → 4
LeetCode 704. The foundation.

javascript

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

Dry run: search([-1,0,3,5,9,12], 9)

code

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

Know this cold. Two iterations for a 6-element array.

Problem 2: Search Insert Position

Problem: Return the index of target, or the index where it would be inserted to keep sorted order.
searchInsert([1,3,5,6], target=5) → 2
searchInsert([1,3,5,6], target=2) → 1
LeetCode 35.

This is lowerBound — Template 2.

javascript

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

Dry run: searchInsert([1,3,5,6], 2)

code

left=0, right=4. mid=2. nums[2]=5 >= 2 → right=2.
left=0, right=2. mid=1. nums[1]=3 >= 2 → right=1.
left=0, right=1. mid=0. nums[0]=1 < 2 → left=1.
left=1 === right=1. return 1. ✓ (2 would be inserted between 1 and 3)

Dry run: searchInsert([1,3,5,6], 7) (insert at end)

code

left=0, right=4. mid=2. nums[2]=5 < 7 → left=3.
left=3, right=4. mid=3. nums[3]=6 < 7 → left=4.
left=4 === right=4. return 4. ✓ (7 goes at the end)

Problem 3: Find First and Last Position (Count Range)

Problem: Find the starting and ending position of a target in a sorted array.
searchRange([5,7,7,8,8,10], target=8) → [3,4]
searchRange([5,7,7,8,8,10], target=6) → [-1,-1]
LeetCode 34.

Four Questions

Q1: What do I have? Sorted array with duplicates.
Q2: What do I want? First and last index of target.
Q3: What is the brute force? Linear scan from left, linear scan from right. O(n).
Q4: Where is the waste? We can find each boundary independently in O(log n) using lowerBound and upperBound.

javascript

function searchRange(nums, target) {
  const first = lowerBound(nums, target);

  // Check if target exists
  if (first === nums.length || nums[first] !== target) return [-1, -1];

  const last = upperBound(nums, target);
  return [first, last];
}

function lowerBound(nums, target) {
  // First index where nums[i] >= target
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

function upperBound(nums, target) {
  // Last index where nums[i] === target
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] <= target) left = mid + 1;  // <= to go past all equals
    else right = mid;
  }
  return left - 1;  // last index with value === target
}

Dry run: searchRange([5,7,7,8,8,10], 8)

lowerBound([5,7,7,8,8,10], 8):

code

left=0, right=6. mid=3. nums[3]=8 >= 8 → right=3.
left=0, right=3. mid=1. nums[1]=7 < 8 → left=2.
left=2, right=3. mid=2. nums[2]=7 < 8 → left=3.
left=3 === right=3. return 3. ✓

upperBound([5,7,7,8,8,10], 8):

code

left=0, right=6. mid=3. nums[3]=8 <= 8 → left=4.
left=4, right=6. mid=5. nums[5]=10 > 8 → right=5.
left=4, right=5. mid=4. nums[4]=8 <= 8 → left=5.
left=5 === right=5. return 5-1=4. ✓

nums[3]=8 ✓ exists. return [3, 4]. ✓

Complexity: O(log n) time, O(1) space.

Problem 4: Search in Rotated Sorted Array

Problem: Search for target in a rotated sorted array. O(log n).
search([4,5,6,7,0,1,2], target=0) → 4
LeetCode 33. Razorpay, Amazon, Google.

Fully developed in Chapter 9. The key: one half is always fully sorted. Determine which half, check if target is in that half, narrow accordingly.

javascript

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

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

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

  return -1;
}

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

code

left=0, right=6. mid=3. nums[3]=7 ≠ 3.
nums[left]=4 <= nums[mid]=7 → left sorted.
Is 4 <= 3 < 7? No. → left=4.

left=4, right=6. mid=5. nums[5]=1 ≠ 3.
nums[left]=nums[4]=0 <= nums[mid]=nums[5]=1 → left sorted.
Is 0 <= 3 < 1? No (3 not < 1). → left=6.

left=6, right=6. mid=6. nums[6]=2 ≠ 3.
nums[left]=2 <= nums[mid]=2 → left sorted.
Is 2 <= 3 < 2? No. → left=7.

left=7 > right=6. return -1. ✓ (3 not in array)

Problem 5: Find Minimum in Rotated Sorted Array

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

Fully developed in Chapter 9. Key: compare nums[mid] with nums[right].

javascript

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

Dry run: findMin([4,5,6,7,0,1,2])

code

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

Problem 6: Koko Eating Bananas

Problem: Koko has piles of bananas, must finish in h hours. Find minimum hourly eating speed.
minEatingSpeed([3,6,7,11], h=8) → 4
LeetCode 875. The gateway to "binary search on answer."

Four Questions

Q1: What do I have? Array of pile sizes, integer h (hours).
Q2: What do I want? Minimum integer speed k such that all piles can be eaten in ≤ h hours.
Q3: What is the brute force? Try k=1, k=2, k=3... until hours ≤ h. O(m × n) where m = max pile.
Q4: Where is the waste? The space of valid k values is monotonic: if k=4 works, k=5 also works. Binary search on k.

javascript

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

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

  return lo;
}

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

code

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=ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3)=1+2+3+4=10 >8 → lo=4.

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

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

lo=4 === hi=4. return 4. ✓

Complexity: O(n log m) — log m binary search iterations, each O(n) to compute hours. n = piles count, m = max pile.

The predicate monotonicity check:

At k=4: 8 hours. Works.
At k=5: 6 hours. Works (and 6 ≤ 8).
At k=3: 10 hours. Fails.
At k=2: too slow. Fails.

Once canDo(k) is true, canDo(k+1) is always true (higher speed = fewer hours). ✓ Monotonic.

Problem 7: Time Based Key-Value Store

Problem: Design a structure supporting set(key, value, timestamp) and get(key, timestamp) — returns the value with the largest timestamp ≤ given timestamp.
LeetCode 981. Google, Airbnb.

Four Questions

Q1: What do I have? Need to store (value, timestamp) pairs per key and retrieve by timestamp range.
Q2: What do I want? For a given key and timestamp, return the value with the largest timestamp ≤ the given timestamp.
Q3: What is the brute force? For each key, store all (timestamp, value) pairs in a list. On get, scan all — O(n) per query.
Q4: Where is the waste? Timestamps are always increasing (given in problem). So for each key, the list is always sorted by timestamp. Binary search for the rightmost timestamp ≤ target: O(log n) per query.

javascript

class TimeMap {
  constructor() {
    this.store = new Map();  // key → [{timestamp, value}] (sorted by timestamp)
  }

  set(key, value, timestamp) {
    if (!this.store.has(key)) this.store.set(key, []);
    this.store.get(key).push({ timestamp, value });
    // Timestamps are always increasing, so this stays sorted.
  }

  get(key, timestamp) {
    if (!this.store.has(key)) return "";
    const records = this.store.get(key);

    // Binary search: find rightmost record with record.timestamp <= timestamp
    let left = 0, right = records.length - 1;
    let result = "";

    while (left <= right) {
      const mid = left + Math.floor((right - left) / 2);
      if (records[mid].timestamp <= timestamp) {
        result = records[mid].value;  // valid candidate
        left = mid + 1;               // try to find a later valid one
      } else {
        right = mid - 1;
      }
    }

    return result;
  }
}

Dry run:

code

set("foo", "bar", 1):  store = {foo: [{t:1, v:"bar"}]}
set("foo", "bar2", 4): store = {foo: [{t:1,v:"bar"},{t:4,v:"bar2"}]}
get("foo", 4): binary search [{t:1},{t:4}] for rightmost <=4.
  left=0, right=1. mid=0. t=1<=4 → result="bar", left=1.
  left=1, right=1. mid=1. t=4<=4 → result="bar2", left=2.
  left=2>right=1. return "bar2". ✓
get("foo", 3): rightmost <=3.
  left=0,right=1. mid=0. t=1<=3 → result="bar", left=1.
  left=1,right=1. mid=1. t=4>3 → right=0.
  left=1>right=0. return "bar". ✓
get("foo", 5): rightmost <=5.
  mid=0: t=1<=5 → result="bar", left=1. mid=1: t=4<=5 → result="bar2", left=2. done.
  return "bar2". ✓
get("foo", 0): no record <=0. result stays "". return "". ✓

Complexity: set O(1), get O(log n) per key. Space O(total sets).

Real-world connection: This is essentially how MVCC (Multi-Version Concurrency Control) works in databases. PostgreSQL stores multiple versions of each row with transaction timestamps. Reading at a given snapshot timestamp queries the version with the largest commit timestamp ≤ snapshot timestamp — binary search over row versions.

Problem 8: Median of Two Sorted Arrays

Problem: Find the median of two sorted arrays in O(log(m+n)).
findMedianSortedArrays([1,3], [2]) → 2.0
findMedianSortedArrays([1,2], [3,4]) → 2.5
LeetCode 4. Hard. Most requested O(log n) problem.

The Insight

The median divides the combined array into two equal halves. If we binary search on how many elements to take from the left portion of array A, the rest of the left half comes from array B.

We want: partitionA elements from A's left + partitionB elements from B's left, where:

partitionA + partitionB = (m + n + 1) / 2 (half the total).
A[partitionA - 1] <= B[partitionB] (left side of A ≤ right side of B).
B[partitionB - 1] <= A[partitionA] (left side of B ≤ right side of A).

Binary search on partitionA from 0 to m (search the smaller array).

javascript

function findMedianSortedArrays(nums1, nums2) {
  // Ensure nums1 is the smaller array
  if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);

  const m = nums1.length, n = nums2.length;
  let lo = 0, hi = m;
  const half = Math.floor((m + n + 1) / 2);

  while (lo <= hi) {
    const partA = Math.floor((lo + hi) / 2);
    const partB = half - partA;

    const leftA  = partA === 0  ? -Infinity : nums1[partA - 1];
    const rightA = partA === m  ?  Infinity : nums1[partA];
    const leftB  = partB === 0  ? -Infinity : nums2[partB - 1];
    const rightB = partB === n  ?  Infinity : nums2[partB];

    if (leftA <= rightB && leftB <= rightA) {
      // Correct partition found
      const maxLeft = Math.max(leftA, leftB);
      if ((m + n) % 2 === 1) return maxLeft;
      return (maxLeft + Math.min(rightA, rightB)) / 2;
    } else if (leftA > rightB) {
      hi = partA - 1;  // take fewer from A
    } else {
      lo = partA + 1;  // take more from A
    }
  }
}

Dry run: findMedianSortedArrays([1,3], [2])

code

m=2, n=1. half=floor(3/2+0.5+1)=floor((3+1)/2)=2. Hmm:
half = floor((2+1+1)/2) = floor(4/2) = 2. ← total left side needs 2 elements.

lo=0, hi=2.

mid iteration:
  partA = floor(1) = 1.
  partB = 2 - 1 = 1.
  leftA  = nums1[0] = 1. rightA = nums1[1] = 3.
  leftB  = nums2[0] = 2. rightB = nums2[1] = ∞ (partB=1=n=1, so Infinity).

  leftA(1) <= rightB(∞) ✓. leftB(2) <= rightA(3) ✓. Partition correct!
  (m+n) % 2 = 3%2 = 1 → odd → return maxLeft = max(1,2) = 2. ✓

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

code

m=2, n=2. half=floor((4+1)/2)=2.

lo=0, hi=2.
partA=1, partB=1.
  leftA=nums1[0]=1. rightA=nums1[1]=2. leftB=nums2[0]=3. rightB=nums2[1]=4.
  leftA(1)<=rightB(4)✓. leftB(3)<=rightA(2)? 3>2. ✗ → lo=2.

lo=2, hi=2.
partA=2, partB=0.
  leftA=nums1[1]=2. rightA=∞. leftB=-∞. rightB=nums2[0]=3.
  leftA(2)<=rightB(3)✓. leftB(-∞)<=rightA(∞)✓. Partition correct!
  (m+n)%2=0 → even → return (max(2,-∞) + min(∞,3))/2 = (2+3)/2 = 2.5. ✓

Complexity: O(log(min(m,n))) — we binary search on the smaller array only.

Why -Infinity and Infinity as sentinels? If partA = 0, there's nothing on the left of A — treat it as negative infinity (anything is larger). If partA = m, there's nothing on the right of A — treat it as positive infinity (nothing from the right of B would cross it).

Pattern Recognition Decision Tree

code

Binary search problem?

1. "Search/find in sorted array" with target value?
   → Standard binary search (Template 1). O(log n).

2. "First/last occurrence" or "count of target"?
   → lowerBound + upperBound (Template 2 + 3). O(log n) each.

3. Rotated sorted array?
   → Determine which half is sorted, check target, narrow. O(log n).

4. "Find minimum/maximum VALUE (not index) that satisfies a condition"?
   → Binary search on answer space. Write canDo(mid), prove monotonicity.
   → Find minimum that works: `if canDo(mid): hi=mid else lo=mid+1`.
   → Find maximum that works: `if canDo(mid): lo=mid+1 else hi=mid`.

5. "Kth smallest in sorted matrix/merged arrays"?
   → Binary search on answer value. Predicate: `countLessOrEqual(mid) >= k`.

6. Historical/versioned data with sorted timestamps?
   → Binary search for rightmost timestamp ≤ query timestamp.

5 Practice Problems

1. Trace and Predict

javascript

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

What does this function return? Trace on [1,2,3,1]. Trace on [1,2,1,3,5,6,4]. What is the loop invariant? What problem does this solve? (LeetCode 162 — Find Peak Element.)

2. Find the Waste

The "capacity to ship packages" problem (LeetCode 1011) and Koko Eating Bananas (LeetCode 875) have identical algorithmic structure. Map one onto the other:

What is "piles" in the shipping problem?
What is "speed k" in the shipping problem?
What is "hours h" in the shipping problem?
Write canShip(capacity).

After writing canShip, plug it into the same binary search template from Koko. What is lo? What is hi? Why?

3. Failure Analysis

javascript

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

Two bugs. Provide a counterexample for each. The correct logic compares nums[mid] with nums[right], not nums[left]. Explain precisely why comparing with nums[left] fails. (What input makes nums[mid] > nums[left] true even when mid is to the left of the minimum?)

4. Design Under Constraints

Design splitArrayLargestSum(nums, k) (LeetCode 410 — Hard): split nums into k non-empty subarrays to minimise the maximum subarray sum.

splitArrayLargestSum([7,2,5,10,8], k=2) → 18

Binary search on the answer (the maximum sum). Write canSplit(maxSum): greedily assign elements to subarrays, incrementing the subarray count when adding the next element would exceed maxSum. If you need ≤ k subarrays, return true. What are lo and hi? Prove monotonicity. Trace two iterations.

5. Reach Beyond

findKthLargest(nums, k) — find the kth largest element in an unsorted array.

There are three approaches:

Sort and index: O(n log n). Trivial.
Min-heap of size k: O(n log k). Practical.
QuickSelect (Chapter 4a practice): O(n) average, O(n²) worst.
Binary search on answer: O(n log(max-min)). count elements ≥ mid, binary search the value space.

Implement approach 4. What is the predicate? What is the search space? When is approach 4 preferable to QuickSelect? (Hint: when elements are integers in a known range and n is very large.)