Binary search fundamentals

Suppose you need to find a value in a sorted array, or the smallest number that satisfies some condition. Checking every candidate in order takes time proportional to the size of the search space. Binary search cuts that space in half on every step, so it finishes in about $\log_2 N$ steps instead of $N$.

Using bisect_left and bisect_right

Python's bisect module already implements binary search over a sorted list. bisect_left(arr, x) returns the leftmost position where x can be inserted without breaking the order. If x is already in the array, that position is the first occurrence. bisect_right(arr, x) returns the position just after the last occurrence instead.

Take the array [1, 2, 2, 2, 3]. bisect_left(arr, 2) returns 1, the index of the first 2. bisect_right(arr, 2) returns 4, the index just past the last 2. Subtracting the two gives the count of 2s in the array: bisect_right(arr, 2) - bisect_left(arr, 2) is 3.

Reach for bisect whenever the array is already sorted and you need the position of a value, or the count of values in some range. It runs in O(log N) and it is part of the standard library, so there is no reason to write the loop by hand for this case.

Binary search on the answer

A different family of problems does not hand you a sorted array at all. Instead, you are asked for the smallest or largest number satisfying some condition, and checking one candidate number costs real work of its own. Say the condition is monotone: once a value works, every larger value also works (or every smaller one does). Then you can binary search directly on the number you are trying to find.

Write a function can_achieve(x) that returns True when x is achievable. Keep two variables: lo, the smallest value you have not ruled out, and hi, one past the largest value you have not ruled out. While lo < hi, compute mid = (lo + hi) // 2. If can_achieve(mid) is True, the answer could be mid or smaller, so set hi = mid. If it is False, mid is too small, so set lo = mid + 1. When the loop ends, lo holds the answer.

A worked example: minimum truck capacity

A delivery truck makes several trips, in order, and cannot reorder the packages waiting for it. Given a fixed number of trips, what is the smallest capacity that still lets every package get delivered?

Checking one candidate capacity is a simple greedy pass: walk through the packages, and start a new trip whenever adding the next package would exceed the capacity. Count how many trips that takes. If a capacity of cap needs 3 trips, then any larger capacity needs 3 trips or fewer, because a bigger truck can only combine loads, never split them further. The condition is monotone in cap, so binary search applies directly to the capacity itself.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    if not input_data:7        return8
9    n = int(input_data[0])10    trips = int(input_data[1])11    weights = [int(x) for x in input_data[2 : 2 + n]]12
13    def trips_needed(cap: int) -> int:14        used = 115        load = 016        for w in weights:17            if load + w > cap:18                used += 119                load = w20            else:21                load += w22        return used23
24    lo = max(weights)25    hi = sum(weights)26
27    while lo < hi:28        mid = (lo + hi) // 229        if trips_needed(mid) <= trips:30            hi = mid31        else:32            lo = mid + 133
34    print(lo)35
36
37if __name__ == "__main__":38    main()

6 3
3 2 2 4 1 4

6

The input gives the package count, the number of trips allowed, and the package weights in delivery order. trips_needed runs the greedy pass for one candidate capacity. The search starts with lo at the heaviest single package, since the truck must carry that package alone at least once. It starts hi at the sum of every weight, since one trip can always carry everything. Each call to trips_needed costs a full pass over the packages, so the whole search runs in O(N log(total weight)), not O(N times every possible capacity).

Why it works

Binary search on the answer relies entirely on monotonicity. Picture every candidate value lined up in order. Because the condition is monotone, the ones that fail come first and the ones that succeed come after, with no failing value appearing after a succeeding one. That single split point is what the search finds.

Checking the midpoint tells you which side of the split point you are on. A failing midpoint means the split point is strictly greater, so lo moves past it. A succeeding midpoint means the split point is at or before it, so hi moves down to it. Each check throws away half of what remains, and after about $\log_2(hi - lo)$ checks only one candidate is left.

This reasoning breaks down the moment the condition stops being monotone. A large value might fail right after a smaller one has already succeeded. The search can converge on the wrong point, or on a point that only looks right because the loop stopped there. Confirm monotonicity on paper, with a couple of concrete numbers, before writing the search.

Loop invariants and off-by-one errors

Binary search is short to write and easy to get subtly wrong. Three mistakes cause most of the bugs.

The loop condition has to be lo < hi, not lo <= hi. With lo == hi, there is nothing left to search. Continuing with lo <= hi on this template invites an infinite loop once lo and hi meet, since neither update always advances past that point.

The update on success has to be hi = mid, not hi = mid - 1. Since mid might be the exact answer, moving hi past it would rule it out. The update on failure has to be lo = mid + 1, not lo = mid, because mid has just been shown not to work, and leaving it in the search space produces an infinite loop.

Integer overflow, the classic C++ trap for mid = (lo + hi) // 2, does not apply in Python: integers here have no fixed size. Floating-point midpoints are a different hazard. Over real numbers instead of integers, rounding error can prevent lo and hi from ever meeting. Stop after a fixed number of iterations instead of waiting for exact equality.

When to reach for which tool

If the data is already sorted and you want a position or a count, call bisect_left or bisect_right directly. If instead you are hunting for a number that satisfies a condition, and testing one candidate is its own small computation, write can_achieve and binary search on the answer. Both are the same halving idea underneath. One searches positions in an array you already have; the other searches values you have not enumerated at all.