Binary Search

Imagine you're guessing a number between 1 and 100. Instead of starting at 1 and going up, you guess 50. Too high? Now you only care about 1–49. Guess 25. Too low? Now it's 26–49. Each guess cuts your options exactly in half.

That's binary search in a nutshell. Instead of checking every item one by one, you always check the middle of what's left — and throw away the half that can't contain your answer.

The catch: the list must be sorted. Without sorting, you can't know which half to discard. Sorting algorithms like merge sort or quicksort can prepare the data in \(O(n \log n)\).

Why it's so fast

After each comparison, half the remaining elements are gone. After 10 comparisons, you've narrowed a list of 1,024 down to just 1. After 30 comparisons, you've searched through one billion elements. That's the power of \(O(\log n)\).

The iterative template

Keep two pointers: lo (left boundary) and hi (right boundary). At each step, compute mid = lo + (hi - lo) / 2 — always write it this way to avoid integer overflow. If arr[mid] equals your target, you're done. If it's too small, move lo = mid + 1. If it's too large, move hi = mid - 1. Loop while lo <= hi.

Finding first or last occurrence

When there are duplicates, don't stop at the first match. To find the leftmost occurrence: when arr[mid] == target, record the index and keep searching left with hi = mid - 1. For the rightmost, record and go right with lo = mid + 1. This is the pattern behind C++'s lower_bound and upper_bound.

Binary Search

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

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(arr, 23))   # 5
print(binary_search(arr, 10))   # -1

Output

5
-1

Complexity

🔍 Search (iterative)30 steps covers 1 billion elements — each step halves the remaining search space

Logarithmic\(O(\log n)\)

🔁 Search (recursive)Identical comparisons but each call adds a frame to the call stack

Same speed, more memory\(O(\log n)\)

💾 Space (iterative)Only lo, hi, and mid variables — no extra memory needed

Constant\(O(1)\)

📚 Space (recursive)Recursion depth equals \(\log_2(n)\) — about 30 frames for a billion elements

Logarithmic stack\(O(\log n)\)

Why it's so fast

The iterative template

Finding first or last occurrence

Binary Search

Complexity

Quick check