Logarithmic Iteration (Binary search patterns)

Logarithmic loops halve or double the index—binary search, exponentiation by squaring, tree height walks. Each step discards half the remaining work.

Why this shows up in the real world

Git bisect halves commits to find a regression. Exponentiation for cryptography uses repeated squaring.

Core idea (explained for students)

Invariant: answer remains inside [lo, hi]. Each iteration picks mid, compares, shrinks interval. Roughly log2(range) steps.

Try this in Python

def bisect_first_ge(a: list[int], x: int) -> int:
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] >= x:
            hi = mid
        else:
            lo = mid + 1
    return lo


print(bisect_first_ge([1, 3, 3, 5], 3))

Common mistakes

• Infinite loop when lo < hi update wrong for boundary duplicates.
• Integer mid bias—use lo + (hi - lo) // 2 to avoid overflow in other languages.

Key takeaways

• Template binary search with clear lo/hi meaning (first true vs last false).
• Practice bisect module for sorted lists in Python.