Binary search variations

Binary search from the beginner track found a value in a sorted list. That is the simplest case. The real power of binary search is broader: any problem where you can answer "is the answer ≥ k?" with a yes/no function can be solved by binary search over k — even when there is no explicit array.

bisect_left and bisect_right

Python's bisect module implements two variants:

• bisect_left(arr, x) — returns the leftmost index where x could be inserted to keep arr sorted. If x is already in arr, returns the index of the first occurrence.
• bisect_right(arr, x) — returns the rightmost index where x could be inserted. If x is already in arr, returns the index after the last occurrence.

from bisect import bisect_left, bisect_right

arr = [1, 2, 2, 2, 3, 4]

bisect_left(arr, 2)    # → 1  (leftmost position for 2)
bisect_right(arr, 2)   # → 4  (rightmost position for 2)

# Count occurrences in O(log n):
count = bisect_right(arr, 2) - bisect_left(arr, 2)   # → 3

# Find leftmost element >= target:
idx = bisect_left(arr, 2)   # → 1; arr[1] == 2 ✓

# Insert while maintaining sort:
import bisect
bisect.insort(arr, 2)   # inserts in correct position — O(n) due to shifting

The two variants are identical on elements not in the array. They differ only when the target is already present, and that difference is load-bearing for "count occurrences" and "find boundary" problems.

Search-space reduction: the unifying pattern

Classic binary search maintains lo and hi and halves the remaining range each step. The invariant is not "the target is in this range" — it is "the answer has not been ruled out of this range." That abstraction generalises far beyond arrays.

Template for "find minimum k satisfying condition C(k)":

def find_minimum(lo, hi, condition):
    """Return the smallest integer k in [lo, hi] where condition(k) is True.
    
    Requires: condition is monotone — once it becomes True, it stays True.
    """
    result = hi + 1   # default: no valid k found
    while lo <= hi:
        mid = (lo + hi) // 2
        if condition(mid):
            result = mid
            hi = mid - 1   # search left for a smaller valid k
        else:
            lo = mid + 1   # mid is too small; search right
    return result

The only requirement on condition is monotonicity: if C(k) is True, then C(k+1) is also True (or equivalently, if C(k) is False, C(k-1) is also False). This structure means the "True region" is a contiguous suffix of the search space and binary search can find its left boundary.

Example: ship packages in D days

Given packages with weights [1, 2, 3, 4, 5] and D=3 days, find the minimum ship capacity so all packages can be loaded in D days. Packages must be loaded in order.

The search space: capacity ranges from max(weights) (must fit the heaviest single package) to sum(weights) (load everything in one day). For any capacity c, testing whether it works is O(n) — simulate loading greedily. C(c) = "capacity c is sufficient" is monotone: if c works, c+1 also works.

Binary search over the capacity range: O(n log(sum - max)) — typically O(n log n) in practice.

def can_ship(weights, capacity, days):
    current_load, day_count = 0, 1
    for w in weights:
        if current_load + w > capacity:
            day_count += 1
            current_load = 0
        current_load += w
    return day_count <= days

def min_ship_capacity(weights, days):
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if can_ship(weights, mid, days):
            hi = mid
        else:
            lo = mid + 1
    return lo

Where to go next

Next: lab — sorting problems — three problems where sorting or binary search is the key move: meeting room scheduling, bisect insertion, and the ship-capacity binary-search-on-answer pattern.