When to Use Binary Search?

Core Idea: Eliminate half the search space each iteration by comparing mid to target or checking a predicate.

Pattern Recognition:

Time Complexity:

O(log n) for search space of size n. Reduces n → n/2 → n/4 → ... → 1

Binary Search (Basic)

O(log n) Time / O(1) Space

Goal: Find target in sorted array, return index or -1.

Technique: Classic Binary Search

Why Binary Search? Array is sorted. Compare mid with target to eliminate half.

Key Insight: If nums[mid] < target, eliminate left half (target must be right). If nums[mid] > target, eliminate right half.

l, r := 0, len(nums)-1 for l <= r: mid := (l + r) / 2 if nums[mid] == target: return mid else if nums[mid] < target: l = mid + 1 // eliminate left half else: r = mid - 1 // eliminate right half return -1

Loop Condition:

Use l <= r to ensure mid is checked when l == r.

Search 2D Matrix

O(log m + log n) Time / O(1) Space

Goal: Search sorted 2D matrix where each row is sorted and first element of each row > last element of previous row.

Technique: Binary Search Row, Then Column

Why Binary Search? Matrix properties guarantee each row is sorted independently. Can binary search to find correct row, then binary search within that row.

Key Insight: Check if row[0] <= target <= row[n-1] to identify correct row. Then standard binary search within row.

for each row: if row[0] <= target && target <= row[last]: l, r := 0, len(row)-1 while l <= r: mid := (l + r) / 2 if row[mid] == target: return true else if row[mid] < target: l = mid + 1 else: r = mid - 1 return false

Alternative:

Treat as flattened 1D array. Convert 1D index to 2D: row = idx / cols, col = idx % cols.

Koko Eating Bananas

O(n log m) Time / O(1) Space

Goal: Find minimum eating speed k to finish all banana piles within h hours.

Technique: Binary Search on Answer

Why Binary Search? We're not searching an array - we're searching the answer space [1, max(piles)]. Define predicate P(k) = "can finish in h hours at speed k". P(k) is monotonic: if P(k) true, then P(k+1) also true.

Key Insight: Search for minimum k where P(k) is true. This is finding the boundary where false → true. When P(mid) is true, search left for smaller k. When false, search right for larger k.

l, r := 1, max(piles) for l <= r: k := (l + r) / 2 totalTime := 0 for pile in piles: totalTime += ceil(pile / k) if totalTime <= h: // P(k) is true r = k - 1 // search for smaller k else: l = k + 1 // need larger k return l // first k where P(k) is true

Binary Search on Answer:

When optimizing "minimize k such that P(k) is true", search answer space [min, max] instead of array indices.

Return Value:

Return l (not r) - l converges to first valid answer where P(k) flips from false to true.

Find Minimum in Rotated Sorted Array

O(log n) Time / O(1) Space

Goal: Find minimum element in sorted array that has been rotated.

Technique: Compare Mid with Right Boundary

Why Binary Search? Rotated sorted array has two sorted segments. Minimum is at the start of the lower segment. Compare nums[mid] with nums[r] to determine which segment mid is in.

Key Insight: If nums[mid] < nums[r], mid is in the lower sorted segment, so minimum is in [l, mid]. If nums[mid] >= nums[r], mid is in upper segment, minimum is in [mid+1, r].

l, r := 0, len(nums)-1 for l < r: // note: l < r, not l <= r mid := (l + r) / 2 if nums[mid] < nums[r]: r = mid // mid could be minimum, keep it else: l = mid + 1 // mid not minimum, eliminate it return nums[l]

Why Compare with Right?

Comparing with nums[r] tells us if we're in the rotated portion. If nums[mid] > nums[r], there's a rotation between mid and r.

Loop Condition:

Use l < r (not l <= r) since we're finding minimum index, not searching for target.

Time-Based Key-Value Store

O(log n) per Get / O(1) Space

Goal: Store values with timestamps and retrieve most recent value ≤ query timestamp.

Technique: Binary Search for Last Valid Timestamp

Why Binary Search? Timestamps are strictly increasing. Want largest timestamp ≤ query. This is "find last occurrence" variant of binary search.

Key Insight: When data[mid].timestamp <= query, it's valid - save it and search right for potentially larger valid timestamp. When > query, search left.

type Data struct { Timestamp int; Value string } type TimeMap struct { Store map[string][]Data } func Get(key, timestamp): data := Store[key] ans := "" l, r := 0, len(data)-1 for l <= r: mid := (l + r) / 2 if data[mid].Timestamp <= timestamp: ans = data[mid].Value // valid, save it l = mid + 1 // search right for larger valid else: r = mid - 1 // too large, search left return ans

Finding Last Valid:

When condition is true, move l = mid+1 (search right). When false, move r = mid-1. Return the saved answer, not l or r.

Binary Search Patterns

1. Classic Search (Find Exact Match):

Use When: Searching for target in sorted array.

Template: if nums[mid] == target return mid, else adjust l/r.

2. Binary Search on Answer:

Use When: Optimizing "minimize/maximize k such that P(k) is true".

Template: Define predicate P(k), search [min_k, max_k] for boundary.

3. Rotated Array:

Use When: Sorted array has been rotated.

Template: Compare mid with boundary to identify which segment.

4. Finding First/Last Occurrence:

First: When condition true, move r = mid-1, return l.

Last: When condition true, move l = mid+1, return saved answer.

Median of Two Sorted Arrays

O(log(min(m,n))) Time / O(1) Space

Goal: Find median of two sorted arrays without merging them.

Why This is Hard:

Can't merge arrays (O(n) time). Must use binary search, but not searching for a value - searching for the correct partition of both arrays that creates a valid left/right split where all left elements < all right elements.

Median Problem: Core Concept

The Partition Approach:

Median means creating a symmetrical split where left half = right half in size (or left has 1 more if odd total).

Key Insight: We need to decide how many elements from each array go into the left partition. If total is 10, we need 5 on left. Maybe 3 from arr1, 2 from arr2. Or 2 from arr1, 3 from arr2. There's exactly ONE valid configuration.

Example - [1,3,4,7,10,12] and [2,3,6,15]:

Total = 10 (even), need 5 on left, 5 on right.

Try: 3 from arr1, 2 from arr2 Left: [1,3,4] from arr1, [2,3] from arr2 Right: [7,10,12] from arr1, [6,15] from arr2 Check symmetry: - arr1 left max (4) <= arr2 right min (6) ✓ - arr2 left max (3) <= arr1 right min (7) ✓ Valid! Median = (max(4,3) + min(7,6))/2 = (4+6)/2 = 5

Symmetry Check:

Cross-compare maximums of left with minimums of right. If both cross-checks pass, all left < all right.

Median Problem: Why Binary Search?

Searching the Partition Space:

Instead of searching array values, we search "how many elements from arr1 go to left partition". Range: [0, len(arr1)].

Always search on the smaller array for better time complexity: O(log(min(m,n))).

Elimination Conditions:

When partition is invalid (symmetry broken), we know which direction to search:

Median Problem: The Algorithm

Setup:

n1, n2 := len(nums1), len(nums2) if n2 < n1: swap(nums1, nums2) // always search smaller n := n1 + n2 left_size := (n + 1) / 2 // works for both even/odd l, r := 0, n1 // search how many from nums1

Binary Search Loop:

for l <= r: i := (l + r) / 2 // take i elements from nums1 j := left_size - i // take rest from nums2 // Get boundary values with sentinel checks aLeft := nums1[i-1] if i > 0 else -∞ aRight := nums1[i] if i < n1 else +∞ bLeft := nums2[j-1] if j > 0 else -∞ bRight := nums2[j] if j < n2 else +∞ // Check symmetry if aLeft <= bRight && bLeft <= aRight: // Valid partition found! if n % 2 == 1: return max(aLeft, bLeft) // odd: left has 1 more else: return (max(aLeft,bLeft) + min(aRight,bRight)) / 2.0 else if aLeft > bRight: r = i - 1 // too many from nums1 else: l = i + 1 // too few from nums1

Median Problem: Detailed Trace

Example: nums1=[7,12,14,15], nums2=[1,2,3,4,9,11]

n1=4, n2=6, total=10 (even), left_size=5

Iteration 1: l=0, r=4, i=2 Take 2 from nums1: [7,12] | [14,15] Take 3 from nums2: [1,2,3] | [4,9,11] aLeft=12, aRight=14, bLeft=3, bRight=4 Check: 12 <= 4? NO Symmetry broken! 12 > 4, too many from nums1 r = i-1 = 1 Iteration 2: l=0, r=1, i=0 Take 0 from nums1: [] | [7,12,14,15] Take 5 from nums2: [1,2,3,4,9] | [11] aLeft=-∞, aRight=7, bLeft=9, bRight=11 Check: -∞ <= 11? YES, 9 <= 7? NO Symmetry broken! 9 > 7, too few from nums1 l = i+1 = 1 Iteration 3: l=1, r=1, i=1 Take 1 from nums1: [7] | [12,14,15] Take 4 from nums2: [1,2,3,4] | [9,11] aLeft=7, aRight=12, bLeft=4, bRight=9 Check: 7 <= 9? YES, 4 <= 12? YES Valid! Even total, so: median = (max(7,4) + min(12,9)) / 2.0 = (7 + 9) / 2.0 = 8.0

Median Problem: Key Formulas

Left Partition Size:

left_size = (n1 + n2 + 1) / 2

Why +1? Works for both even and odd totals. If total=10, gives 5. If total=11, gives 6 (left has 1 more).

Median Calculation:

Odd total (left has 1 extra):

median = max(aLeft, bLeft)

The maximum of the left partition is the middle element.

Even total (equal split):

median = (max(aLeft, bLeft) + min(aRight, bRight)) / 2.0

Average of largest left element and smallest right element.

Sentinel Values:

When i=0 (no elements from arr1 on left), aLeft = -∞ so it doesn't affect max().

When i=n1 (all elements from arr1 on left), aRight = +∞ so it doesn't affect min().

Median Problem: Why Left Partition?

The Symmetry Principle:

If we know the correct left partition, we automatically know the right partition (everything else).

By using (n1+n2+1)/2, we ensure:

This formula handles both cases uniformly in the binary search loop.

Cross-Comparison Insight:

We don't need to check aLeft <= aRight or bLeft <= bRight because arrays are already sorted internally.

We ONLY check the cross boundaries: aLeft <= bRight and bLeft <= aRight. These are the "walls" between our partition.

Median Problem: Common Pitfalls

1. Not searching on smaller array:

Time complexity becomes O(log(max(m,n))) instead of O(log(min(m,n))).

2. Wrong partition size formula:

Using n/2 instead of (n+1)/2 breaks odd case.

3. Forgetting sentinels:

When i=0 or j=0, arrays have no left element. When i=n1 or j=n2, no right element. Must use -∞/+∞.

4. Wrong elimination logic:

If aLeft > bRight, must reduce i (fewer from arr1). If bLeft > aRight, must increase i (more from arr1).

5. Integer division for median:

For even totals, remember to divide by 2.0 (float) not 2 (int) to get correct decimal result.