DSA · Chapter 34 of 40

Binary Search

Binary search finds a target in a sorted array by repeatedly halving the search range, giving O(log n) time. Each step compares the middle element with the target and discards one half.

Most binary search bugs come from the loop condition and the mid calculation, so use low <= high with mid = low + (high - low) // 2.

Boundary variants

Finding the first or last occurrence of a value requires continuing the search after a match instead of returning immediately.

Requirements

The data must be sorted or at least monotonic with respect to the condition you test.

Example 1 (python)

def bsearch(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
print(bsearch([1, 3, 5, 7, 9], 7))

Output

Each comparison removes half the remaining range.

Example 2 (python)

def first_occurrence(a, t):
    lo, hi, res = 0, len(a) - 1, -1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == t:
            res = mid
            hi = mid - 1
        elif a[mid] < t:
            lo = mid + 1
        else:
            hi = mid - 1
    return res
print(first_occurrence([1, 2, 2, 2, 3], 2))

Output

Keep searching left after a match to find the first index.

Key points

Binary search is O(log n) on sorted data.
Use mid = low + (high - low) // 2 to avoid overflow.
First/last occurrence variants keep searching after a match.
The data must be sorted or monotonic.

💡 Note: Write the loop invariant before coding: which range still might contain the answer?

Binary Search

Boundary variants

Requirements

Key points

📝 Quick Quiz