Repeatedly halve the search space on a monotone predicate. O(log N).

Data Flow

target = 10
sorted:  [1, 3, 5, 7, 9, 11, 13]

mid=3 arr[mid]=7   too low  -> lo=4
mid=5 arr[mid]=11  too high -> hi=4
mid=4 arr[mid]=9   too low  -> lo=5
lo > hi -> not found

When to use

• Sorted array or monotone predicate (f(mid) is True for all m >= T).
• “Find the minimum maximum” or “smallest X such that condition holds”.

Code (last false / first true)

def bsearch(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < target:  lo = mid + 1
        else:                  hi = mid
    return lo                          # first idx >= target

Pitfalls

• Off-by-one on lo <= hi vs lo < hi — pick one style and stick with it.
• Integer overflow on mid = (lo + hi) // 2 in fixed-width ints — use lo + (hi - lo) // 2.

Analogy

Looking up a word in a physical dictionary: open the middle, decide left or right, repeat.

Interview tip: If asked “minimum/maximum of something monotone”, do NOT simulate. Binary-search the answer.