Why Binary Search

Binary search is O(log n) — the most efficient search for sorted data. Google expects you to implement it from scratch and apply it to non-obvious situations.

The Template

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2  # Avoids integer overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1   # Target is in right half
        else:
            right = mid - 1  # Target is in left half

    return -1  # Not found

The mid calculation: Use left + (right - left) // 2 instead of (left + right) // 2 to avoid integer overflow. In Python, integers can be arbitrarily large so this isn’t technically needed, but Google loves seeing you know this. In C#/Java/TypeScript it matters.

Common Variants

  1. Find leftmost/rightmost occurrence: Modify what happens when arr[mid] == target

  2. Search in rotated sorted array: Modified binary search with an extra condition

  3. Search on answer space: Binary search on the ANSWER, not the array (e.g., "what’s the minimum capacity?")

Exercises

  • Binary Search — Standard, leftmost, rightmost, and rotated sorted array variants