Binary search, from guessing games to lower bounds

Definition

Binary search is an algorithm that finds the position of a target value within a sorted collection by repeatedly dividing the search space in half. At each step, it compares the target value to the middle element to determine whether the target lies in the left half or the right half.

Analogy

Imagine looking up a word in a printed dictionary. You do not read every page from the beginning; instead, you open the book roughly in the middle. If the target word comes before the words on that middle page alphabetically, you discard the entire back half of the book and repeat the process on the front half. If it comes after, you discard the front half. You repeat this halving process until you land on the exact page. This analogy breaks down because human page-turning does not divide the page count exactly in half every turn, whereas the algorithm strictly calculates the exact midpoint.

Before you start

• Basic knowledge of indexed arrays or lists
• Understanding of conditional statements and loops
• Familiarity with comparison operations (less than, greater than, equal to)

Level 1 · Beginner: The halving mechanism and a manual walk-through

When searching an unsorted list of items, you must examine every item one by one until you find the target or reach the end. This linear scan requires work proportional to the number of items. When the collection is already sorted, you can make a much faster decision by inspecting the item in the exact center.

Consider searching for the number 7 in the sorted array [1, 3, 5, 7, 9, 11, 13]. The array has 7 elements, indexed from 0 to 6. We place two markers: left at index 0 and right at index 6. The middle index is (0 + 6) // 2, which is 3. The value at index 3 is 7. Because the middle element equals our target, the search completes in a single step.

Now suppose we search for 11 in that same array. Left is 0, right is 6, and middle is 3 (value 7). Because 11 is greater than 7, the target cannot exist at index 3 or any index to its left. We discard the left half by setting left to middle + 1, which is 4. The search interval is now index 4 to 6. The new middle is (4 + 6) // 2, which is 5. The value at index 5 is 11, matching our target after two inspections.

If the target were not in the array, say 8, the pointers would eventually cross. Once left exceeds right, the search space is empty, meaning the target does not exist in the collection.

Basic iterative binary search returning the index of the target or -1

def binary_search(nums: list[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1

Key takeaways

• The collection must be sorted before binary search can work.
• Every comparison eliminates half of the remaining elements.
• The loop terminates when the target is found or when left exceeds right.

Level 2 · Intermediate: Defensive boundaries, edge cases, and bisect logic

Writing binary search correctly requires strict adherence to invariant conditions. In the standard search, the invariant is that the target, if present, resides within the closed interval [left, right]. Every step must preserve this invariant while shrinking the interval by at least one element to guarantee termination.

An edge case occurs when the input list is empty. In that scenario, left starts at 0 and right starts at -1. The condition left <= right evaluates to false immediately, returning -1 safely without out-of-bounds indexing.

Another consideration in languages with fixed-width integers (such as C++ or Java) is integer overflow during the midpoint calculation. Writing mid = left + (right - left) // 2 prevents the addition of left + right from exceeding standard 32-bit limits. While Python handles arbitrarily large integers automatically, adopting this formula maintains cross-language consistency.

Collections often contain duplicate elements. When duplicates exist, the standard search may return any matching index. To find the first occurrence (lower bound) or the point where a new element should be inserted, the search condition is modified: when nums[mid] >= target, we continue searching in the left half to locate the earliest possible index.

Binary search variant finding the first occurrence of a target in a sorted list

def find_first_occurrence(nums: list[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            result = mid
            right = mid - 1
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return result


def test_first_occurrence():
    assert find_first_occurrence([], 5) == -1
    assert find_first_occurrence([2], 2) == 0
    assert find_first_occurrence([2], 3) == -1
    assert find_first_occurrence([1, 2, 2, 2, 3], 2) == 1
    assert find_first_occurrence([1, 2, 3, 4, 5], 1) == 0
    assert find_first_occurrence([1, 2, 3, 4, 5], 5) == 4

test_first_occurrence()

Key takeaways

• Use left + (right - left) // 2 to avoid integer overflow in fixed-width environments.
• Preserve the search interval invariant to eliminate off-by-one infinite loops.
• To find boundaries with duplicate elements, record candidate matches and narrow the range.

Level 3 · Advanced: Binary search on monotonic answer spaces

Binary search is not restricted to arrays stored in memory. It applies to any monotonic predicate, a boolean function f(x) that returns false for all values up to a certain point and true for all values after (or vice versa). Instead of searching an array, we search over a range of possible answers.

Consider the problem of determining the minimum capacity of a conveyor belt required to ship packages within D days. If capacity C is sufficient to ship the items within D days, any capacity greater than C is also sufficient. Conversely, if capacity C is too small, any smaller capacity will also fail. This monotonic property allows us to binary search the answer between the maximum single item weight and the sum of all item weights.

When working with continuous domains (floating-point numbers), pointer equality like left <= right is replaced by an epsilon threshold, such as while (right - left) > 1e-7, or by running the loop for a fixed number of iterations (for example, 60 to 100 iterations), which provides exact precision without convergence stalling.

The limitation of binary search lies in its dependency on monotonicity. If the predicate or data order fluctuates non-monotonically, binary search cannot guarantee finding the correct element, and full exploration or heuristic search techniques must be used instead.

Binary search on the answer space to find minimum capacity to ship packages

def can_ship(weights: list[int], days: int, capacity: int) -> bool:
    days_needed = 1
    current_load = 0
    for w in weights:
        if current_load + w > capacity:
            days_needed += 1
            current_load = w
        else:
            current_load += w
    return days_needed <= days


def ship_within_days(weights: list[int], days: int) -> int:
    left = max(weights)
    right = sum(weights)
    ans = right
    
    while left <= right:
        mid = left + (right - left) // 2
        if can_ship(weights, days, mid):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
            
    return ans

Key takeaways

• Any problem with a monotonic feasibility function can be solved via binary search on the answer.
• Floating-point binary search should use a fixed iteration count or an epsilon bound.
• Binary search cannot be applied directly when the underlying condition lacks monotonicity.

Complexity

• Time: O(1) best case, O(log n) average and worst case
• Space: O(1) auxiliary space

At each step, the search interval size n is halved (n / 2, n / 4, ...). The interval reduces to a single element in at most log2(n) comparisons. Iterative binary search uses only a constant number of pointer variables, requiring no additional memory.

Common mistakes

• Running binary search on an unsorted collection, which invalidates the assumption that elements to the left or right can be safely discarded.
• Off-by-one errors in pointer updates, such as setting left = mid or right = mid in inclusive loops, causing an infinite loop when the interval size is two.
• Using left < right instead of left <= right for simple target lookup, causing the algorithm to skip inspecting the final remaining candidate element.
• Potential 32-bit integer overflow when calculating mid = (left + right) // 2 in languages with fixed-size integers.

Practice problems

1. Search Insert Position (easy). Hint: Track where the left pointer ends up after the search loop terminates without finding the target.
2. Find First and Last Position of Element in Sorted Array (medium). Hint: Run two separate binary searches: one that continues searching left on match, and one that continues searching right.
3. Koko Eating Bananas (medium). Hint: The eating speed ranges from 1 to the maximum pile size; binary search for the minimum valid speed.
4. Median of Two Sorted Arrays (hard). Hint: Binary search the partition cut of the smaller array such that the combined left half contains half of all elements.

Summary

Binary search is an optimal divide-and-conquer strategy that achieves logarithmic time by discarding half the remaining search space with each comparison. Beginning with simple array searches, its invariant-based approach extends to finding boundaries among duplicates and solving complex optimization problems over monotonic answer spaces.