Binary Search

Use when: Sorted array, or monotonic condition where you can binary search on the answer.

Complexity: O(log N)

Standard - Search in Sorted Array

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Find Leftmost (First True)

# Find smallest index where condition is True
lo, hi = 0, len(nums) - 1
ans = -1
while lo <= hi:
    mid = (lo + hi) // 2
    if condition(mid):
        ans = mid
        hi = mid - 1  # go left to find earlier
    else:
        lo = mid + 1
return ans

Find Rightmost (Last True)

lo, hi = 0, len(nums) - 1
ans = -1
while lo <= hi:
    mid = (lo + hi) // 2
    if condition(mid):
        ans = mid
        lo = mid + 1  # go right to find later
    else:
        hi = mid - 1
return ans

Binary Search on Answer

# When the answer space is monotonic (feasible/not feasible)
lo, hi = min_possible, max_possible
while lo <= hi:
    mid = (lo + hi) // 2
    if feasible(mid):
        ans = mid
        lo = mid + 1  # try higher
    else:
        hi = mid - 1
return ans

Signals in a Problem

• Sorted input
• “Minimize the maximum” / “Maximize the minimum”
• Search space has a monotonic feasibility condition