Binary Search

Binary search applies when a predicate over a sorted domain is monotonic. The invariant is that the answer always lies within [lo, hi].

Pattern A: Lower bound / insertion position

Use when: you need the first index where nums[i] >= target.

Invariant: all indices < lo are < target, all >= hi are >= target.

Skeleton:

lo = 0; hi = n
while lo < hi:
    mid = lo + (hi-lo)/2
    if nums[mid] < target: lo = mid + 1
    else: hi = mid
return lo

Problems:

• search-insert-position.

Pattern B: Binary search on a virtual array

Use when: a 2D matrix is sorted row-major.

Invariant: map mid to (r,c) by r = mid / n, c = mid % n.

Skeleton:

lo = 0; hi = m*n - 1
while lo <= hi:
    mid = (lo+hi)/2
    r = mid / n; c = mid % n
    compare matrix[r][c] with target

Problems:

• search-a-2d-matrix.

Pattern C: Peak search by slope

Use when: you need a local maximum with neighbors.

Invariant: if nums[mid] < nums[mid+1], peak is to the right.

Skeleton:

lo = 0; hi = n-1
while lo < hi:
    mid = (lo+hi)/2
    if nums[mid] < nums[mid+1]: lo = mid + 1
    else: hi = mid
return lo

Problems:

• find-peak-element.

Pattern D: Rotated array decision

Use when: sorted array is rotated by an unknown pivot.

Invariant: one half is still sorted.

Skeleton (search):

while lo <= hi:
    mid = (lo+hi)/2
    if nums[mid] == target: return mid
    if nums[lo] <= nums[mid]:
        if nums[lo] <= target < nums[mid]: hi = mid-1
        else: lo = mid+1
    else:
        if nums[mid] < target <= nums[hi]: lo = mid+1
        else: hi = mid-1

Skeleton (min):

while lo < hi:
    mid = (lo+hi)/2
    if nums[mid] > nums[hi]: lo = mid+1
    else: hi = mid
return nums[lo]

Problems:

• search-in-rotated-sorted-array.
• find-minimum-in-rotated-sorted-array.

Pattern E: First/last occurrence

Use when: duplicates exist and you need the full range.

Invariant: two bounds define the leftmost and rightmost positions.

Skeleton:

left = lower_bound(target)
right = lower_bound(target+1) - 1

Problems:

• find-first-and-last-position-of-element-in-sorted-array.

Pattern F: Partition by count (median of two arrays)

Use when: you can partition two sorted arrays into left/right halves.

Invariant: maxLeft <= minRight across the partition.

Skeleton:

// binary search on smaller array A
while true:
    i = mid in A
    j = (m+n+1)/2 - i
    if A[i-1] <= B[j] and B[j-1] <= A[i]: found partition
    else adjust i

Problems:

• median-of-two-sorted-arrays.

When to use Binary Search (checklist)

• The search space is sorted or monotonic.
• You can define a predicate that flips from false to true.

Common failures (checklist)

• Infinite loops from incorrect mid updates.
• Overflow in mid calculation (use lo + (hi-lo)/2).
• Off-by-one mistakes in inclusive vs exclusive bounds.

Problem mapping

• search-insert-position: lower bound.
• search-a-2d-matrix: virtual array search.
• find-peak-element: slope-based search.
• search-in-rotated-sorted-array: sorted-half logic.
• find-first-and-last-position-of-element-in-sorted-array: two bounds.
• find-minimum-in-rotated-sorted-array: min by pivot search.
• median-of-two-sorted-arrays: partition by counts.