Binary Search — Halving the Problem

What is it? #

Binary search finds an item in sorted data by repeatedly cutting the search area in half.

Look at the middle. If it matches, you are done. If your target is smaller, everything to the right is irrelevant, so discard it. If larger, discard the left. Repeat.

Each step halves what remains, which is why a million items take about twenty steps. That is O(log n).

There is one hard requirement: the data must be sorted. Binary search on unsorted data returns wrong answers silently, which is worse than failing.

Think of it like this #

Guessing a number between 1 and 100. Guessing 1, 2, 3 in order takes up to a hundred tries.

Guessing 50 and being told "higher" eliminates half the range immediately. Then 75, then 62. Seven guesses cover a hundred numbers; ten cover a thousand.

Simple example #

You have a sorted list of a million timestamps and need to find the position of a specific one — or, more usefully, the first entry after a given time. Scanning is slow; binary search is instant.

Code #

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2        # integer division
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1              # discard the left half
        else:
            high = mid - 1             # discard the right half
    return -1                          # not found


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


# Finding the insertion point — often more useful than exact match
import bisect

print(bisect.bisect_left(nums, 24))    # 6 — where 24 would go
print(bisect.bisect_left(nums, 23))    # 5 — first position of 23
bisect.insort(nums, 24)                # insert while keeping order
print(nums)


# Binary search on an answer, not a list
def min_ships_needed(weights, days):
    """Smallest ship capacity that moves all weights within the given days."""
    def days_required(capacity):
        days_used, load = 1, 0
        for weight in weights:
            if load + weight > capacity:
                days_used += 1
                load = 0
            load += weight
        return days_used

    low, high = max(weights), sum(weights)
    while low < high:
        mid = (low + high) // 2
        if days_required(mid) <= days:
            high = mid                 # mid works, try smaller
        else:
            low = mid + 1              # mid too small
    return low


print(min_ships_needed([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))   # 15

Searching 1,000,000 sorted items

linear scan     up to 1,000,000 comparisons
binary search   about 20 comparisons

How it works #

low and high mark the range still under consideration. The loop runs while that range is non-empty.

mid = (low + high) // 2 picks the middle. Comparing items[mid] with the target tells you which half to throw away — and throwing away half is the entire algorithm.

low = mid + 1 and high = mid - 1 are the details people get wrong. Using mid instead of mid + 1 can leave the range unchanged and loop forever. Always move past the element you just checked.

bisect_left answers a more useful question than "is it here": it returns where the value belongs. That lets you find the first item at or after a value, which is what range queries need.

The last function shows a technique worth knowing: binary searching over a range of possible answers rather than over a list. If a candidate answer is checkable and the answers are monotonic — if capacity 20 works, 21 works too — you can binary search the answer space. This shape appears often in optimisation problems.

The loop there uses while low < high with high = mid, which converges on the smallest working value. That variant is worth learning separately from the exact-match version.

Real-world use #

Database indexes are binary search made durable. A B-tree index narrows down rows the same way, which is why an indexed lookup on ten million rows is instant and a full scan is not.

Version control tools use it directly: git bisect finds the commit that introduced a bug by testing the middle commit and discarding half the history each time. Fifteen tests cover 30,000 commits.

Autocomplete and range queries use bisect-style searches over sorted data to find the first match at or after a prefix.

The prerequisite is the catch. Keeping data sorted has its own cost, so binary search pays off when you read far more often than you write — which is exactly the trade-off a database index makes.

Common mistakes #

• Running it on unsorted data, which returns wrong results silently.
• Writing low = mid instead of low = mid + 1, causing an infinite loop.
• Getting the boundary wrong with < versus <= and missing the last element.
• Sorting inside a loop just to binary search, which costs more than scanning.
• Writing it by hand in Python when bisect already does it correctly.

Practice #

Implement first_occurrence(items, target) that returns the index of the first matching element in a sorted list with duplicates (not just any match). Then use bisect to write count_in_range(items, low, high) that counts values in a range without scanning.