Binary Search

Binary search is the art of cutting your problem in half with each step. Instead of checking every element (O(n)), you eliminate half the remaining options each time (O(log n)). A million elements? Just 20 comparisons.

The Core Idea

If your data is sorted (or has some monotonic property), you can make smart decisions about where to look next. Check the middle - if it's too big, search left; if too small, search right.

The Classic Template

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

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # Not found

Finding Boundaries

Often you need the first or last occurrence, not just any match. Here's how to find the leftmost (first) position:

def leftmostPosition(arr, target):
    left, right = 0, len(arr)

    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid  # Don't exclude mid yet

    return left

Binary Search on Answer

This is where it gets interesting. Sometimes you binary search not on an array, but on the possible answers. "What's the minimum capacity to ship packages in D days?" becomes "can we ship with capacity X in D days?"

def minCapacity(weights, days):
    def canShip(capacity):
        # Check if this capacity works
        day_count = 1
        current = 0
        for w in weights:
            if current + w > capacity:
                day_count += 1
                current = 0
            current += w
        return day_count <= days

    # Binary search on capacity
    left = max(weights)
    right = sum(weights)

    while left < right:
        mid = (left + right) // 2
        if canShip(mid):
            right = mid
        else:
            left = mid + 1

    return left

Common Pitfalls

• Integer overflow - Use left + (right - left) // 2 in some languages
• Off-by-one errors - Should right be len-1 or len?
• Infinite loops - Make sure the search space shrinks each iteration