Binary Search: More Than Just "Find X

What Binary Search Actually Does

Imagine you're looking for a word in a physical dictionary. You don't start at page one and flip forward one page at a time — you open to the middle, decide whether your word comes before or after, and discard half the book. That's binary search: repeatedly halving the search space until only the answer remains.

In code, binary search applies whenever your search space is monotonic — meaning it follows a consistent pattern like "all valid on the left, all invalid on the right" or vice versa. The classic case is finding a number in a sorted array, but the real power is using it to search over answers, not just indices.

The Framework

Binary Search is the first algorithm you must master because it turns $O(N)$ problems into $O(\log N)$ problems. It is not just for finding a number in a sorted array; it is for finding a boundary in any monotonic search space.

The Golden Rule: If the search space is sorted (or follows a pattern like T, T, T, F, F, F), use Binary Search.

The Template

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2   # overflow-safe midpoint
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1   # not found

The "Mid" Bug
A classic junior mistake is calculating the midpoint as (left + right) / 2. In languages like C++ or Java, this causes an integer overflow if left + right exceeds the maximum integer limit (roughly 2.1 billion for a 32-bit signed integer). Python's integers are arbitrary-precision so overflow isn't a concern there, but the safe formula is a good habit in any language.

• Correct Formula: mid = left + (right - left) // 2

Searching Over the Answer Space

Many problems don't ask you to search an array at all — they ask you to find the minimum value that satisfies some condition. For example: "What is the minimum number of days to ship all packages if each ship has capacity C?" You binary search over possible values of C (from max(weights) to sum(weights)), and for each candidate you check whether it works. This pattern appears constantly in system-design-adjacent coding questions.

# Pattern: binary search on the answer
def feasible(capacity, weights, days):
    current_load, days_needed = 0, 1
    for w in weights:
        if current_load + w > capacity:
            days_needed += 1
            current_load = 0
        current_load += w
    return days_needed <= days

def ship_within_days(weights, days):
    left, right = max(weights), sum(weights)
    while left < right:
        mid = left + (right - left) // 2
        if feasible(mid, weights, days):
            right = mid          # mid might be the answer; don't discard it
        else:
            left = mid + 1
    return left