5 Binary Search Variations Worth Memorizing

1. Classic: find an exact target in a sorted array and return its index, or -1.

• Stop as soon as nums[mid] == target
• Loop while lo <= hi

2. Leftmost occurrence: return the first position where the target appears, or where it would be inserted.

• Move hi = mid when nums[mid] >= target
• When the loop ends, lo is the left boundary

3. Rightmost occurrence: return the last position where the target appears, by finding the first value larger than it.

• Move lo = mid + 1 when nums[mid] <= target
• The answer is lo - 1

4. Search on a range: look for the smallest answer that satisfies a condition, with no array involved.

Many "minimum capacity" and "minimum speed" problems are this variation in disguise. The answer lies between a known low and high value, and the condition you test only flips once inside that range. Binary search finds that flip point.

• Write a helper works(x) that returns True or False
• The condition must be false, then true, never back again

5. 2D matrix: treat a sorted matrix as one long sorted array.

• Map a flat index to a cell with row, col = divmod(mid, cols)
• Everything else is the classic search

Notes:

• The hardest part of binary search is not the idea but the boundaries. Always test the empty array, one element, and a target outside the range.
• If you get stuck, write out the loop by hand on a three element array.

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

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

while lo < hi:
    mid = (lo + hi) // 2
    if works(mid):
        hi = mid
    else:
        lo = mid + 1
return lo   # smallest that works

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

cols = len(grid[0])
lo, hi = 0, len(grid) * cols - 1
while lo <= hi:
    mid = (lo + hi) // 2
    r, c = divmod(mid, cols)
    if grid[r][c] == target:
        return True
    if grid[r][c] < target:
        lo = mid + 1
    else:
        hi = mid - 1
return False