Searching sorted data cheat sheet

Where would a new price go in a sorted list?

Binary search with a half-open range. Keep the invariant that the answer lies in [lo, hi]: if prices[mid] is below the target, the answer is right of mid, so lo = mid + 1; otherwise mid itself could be the answer, so hi = mid. The range halves each step, giving O(log n) time and O(1) space.

def first_at_least(prices: list[int], target: int) -> int:
    lo, hi = 0, len(prices)  # the answer is always in [lo, hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if prices[mid] < target:
            lo = mid + 1
        else:
            hi = mid  # mid itself may be the answer
    return lo

Slowest reading pace that still finishes on time

Faster paces never take longer, so 'finishes in time' flips from False to True exactly once as p grows. Binary search p between 1 and the biggest chapter, testing each candidate in O(n). Total O(n log m) where m is the largest chapter, with O(1) extra space.

def slowest_pace(chapters: list[int], hours: int) -> int:
    def hours_needed(pace: int) -> int:
        return sum(-(-pages // pace) for pages in chapters)

    lo, hi = 1, max(chapters)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours_needed(mid) <= hours:
            hi = mid
        else:
            lo = mid + 1
    return lo

Smallest value in a rotated sorted list

Compare the middle value with the last value. If the middle is bigger, the drop (and the minimum) is to its right; otherwise the minimum is at mid or to its left. Shrink towards it until lo meets hi. O(log n) time, O(1) space.

def rotated_min(vals: list[int]) -> int:
    lo, hi = 0, len(vals) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if vals[mid] > vals[hi]:
            lo = mid + 1  # the drop is to the right of mid
        else:
            hi = mid
    return vals[lo]

Find a value in a rotated sorted list

At each step at least one half around mid is sorted. If the left half is sorted (vals[lo] <= vals[mid]) and the target lies inside it, search there; otherwise search the right. Mirror the logic when the right half is sorted. O(log n) time and O(1) space.

First and last position of a value in a sorted list

Run two lower-bound searches: the first index with value >= target, and the first index with value >= target + 1 (for integers), minus one. If the first index is out of range or holds a different value, the target is absent. Two O(log n) searches and O(1) extra space.

Whole-number square root without math.sqrt

Search r in [0, n] for the last value whose square is at most n. Squares grow with r, so the test flips from True to False once. Binary search finds the boundary in O(log n) steps with O(1) space. Python's big integers mean the squares never overflow.

def whole_sqrt(n: int) -> int:
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi + 1) // 2  # round up so lo = mid always moves
        if mid * mid <= n:
            lo = mid
        else:
            hi = mid - 1
    return lo

Smallest truck that delivers every parcel in d days

A bigger truck never needs more days, so binary search the capacity between the heaviest parcel and the total weight. For a candidate, a greedy pass counts days by filling the truck until the next parcel would overflow. O(n log S) where S is the total weight, with O(1) extra space.

Highest point of a climb-then-descent route

Compare alt[mid] with alt[mid + 1]. If the route is still rising there, the summit is to the right; otherwise it is at mid or to the left. Shrink until lo meets hi. Each step halves the range: O(log n) time, O(1) space.

def summit_index(alt: list[int]) -> int:
    lo, hi = 0, len(alt) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if alt[mid] < alt[mid + 1]:
            lo = mid + 1  # still climbing
        else:
            hi = mid
    return lo

Find a value in a grid sorted row after row

Read the grid as one sorted list of R·C values: position k is row k // C, column k % C. Binary search that virtual list in O(log(R·C)) time with O(1) extra memory.

Binary search without off-by-one bugs

Most bugs come from mixing conventions: closed ranges [lo, hi] with while lo <= hi and hi = mid - 1, versus half-open ranges [lo, hi) with while lo < hi and hi = mid. Pick one, write the invariant ('the answer is always in this range'), and check every branch keeps it true and shrinks the range. Then the loop ends with the answer at lo.

Binary search on the answer

Instead of searching a list, search the range of possible answers. It works when you can check a candidate quickly and the check is monotonic: once a value works, every larger (or smaller) value works too. The search finds the boundary in O(log range) checks, each costing whatever the check costs.

Using bisect and sorted lists in practice

bisect_left and bisect_right find positions in a sorted list in O(log n). insort finds the spot in O(log n) but inserting into a list shifts items, so each insert is O(n). For many inserts and lookups together, use a balanced tree or a sorted-container library; for a fixed sorted list, bisect is ideal.