Patterns

Binary search

Binary search finds a boundary inside a range that has an order. The order is the part people forget. The halving is the easy part. If you cannot point at a rule that says "everything left of here is too small and everything right of here is large enough," you do not have a binary search. You have a loop that happens to look like one.

The classic setting is a sorted array. A second setting, often more useful in interviews, is searching over the answer itself: the smallest capacity, the lowest speed, the earliest day, provided that "can I succeed at this number?" flips from no to yes exactly once as the number grows. Both settings are below, with original tasks. Neither task is an assessment prompt.

Two pointers also like sorted data, but they walk an array looking for a pair. Binary search throws away half of a range on each step because of a yes-or-no test. Do not mix the vocabulary. If you hear yourself say "I'll binary search" while moving two ends based on a sum, you are describing pointers.

Search in a sorted list

Original task: notebook page numbers are sorted ascending and may contain duplicates. Return the smallest index whose page number is at least the target. If every page number is smaller, return the length of the list. This is a lower bound, not a boolean.

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


assert first_at_least([1, 3, 3, 7], 3) == 1
assert first_at_least([1, 3, 3, 7], 4) == 3
assert first_at_least([1, 3, 3, 7], 8) == 4
assert first_at_least([], 1) == 0

right starts at len(pages), one past the last index. That sentinel is how "not found" falls out naturally as the insertion point. The loop keeps the invariant that the answer is inside the half-open range [left, right). If the middle page is strictly below the target, the answer cannot be mid or anything left of it, so left becomes mid + 1. Otherwise mid might be the answer, so right becomes mid and you do not skip it.

Each step halves the range, so the number of steps is logarithmic in the number of pages. Each step reads one element. Total time is logarithmic. Extra space is constant. A linear scan is correct and easier to write. Mention it, then say why you are halving: the caller said the pages are sorted, and n may be large.

The bug that shows up in interviews is right = mid - 1 copied from a version that searched for an exact match and discarded mid. In a lower-bound search, mid is still a candidate when pages[mid] >= target. Discarding it returns the wrong index on the first assert: the first 3 would be skipped. Write the invariant in a comment if you are tired. Comments are cheaper than a wrong boundary.

Also notice integer division. (left + right) // 2 is safe in Python because integers do not overflow. In languages with fixed-width integers, left + (right - left) // 2 is the form that does not overflow. If you interview in more than one language, know which form you are using. The logic is the same.

Search on the answer

Sometimes the array is not sorted in a way you can probe, but the answer is a number inside a range, and feasibility is monotonic. "If I can do it with capacity c, I can do it with anything larger." Then the smallest feasible c is a boundary, and binary search applies to c, not to the array indexes.

Original task: you must copy files onto drives in the order given. Each drive has the same capacity. A file cannot be split. Find the smallest capacity that lets you finish with at most drive_count drives. Assume there is at least one file and at least one drive.

def min_drive_capacity(files: list[int], drive_count: int) -> int:
    def fits(capacity: int) -> bool:
        drives_used = 1
        filled = 0
        for size in files:
            if size > capacity:
                return False
            if filled + size <= capacity:
                filled += size
            else:
                drives_used += 1
                filled = size
        return drives_used <= drive_count

    low, high = max(files), sum(files)
    while low < high:
        mid = (low + high) // 2
        if fits(mid):
            high = mid
        else:
            low = mid + 1
    return low


assert min_drive_capacity([4, 2, 3], 2) == 5
assert min_drive_capacity([4, 2, 3], 3) == 4
assert min_drive_capacity([5], 1) == 5

Walk [4, 2, 3] with two drives. Capacity 4 fails because the 4 fills a drive and 2 + 3 = 5 needs another drive that is too small, so you would need three drives. Capacity 5 works: 4 on the first drive, 2 and 3 on the second. Capacity 9 also works and is wasteful. The search returns 5.

The low end of the range is the largest single file, because a drive must hold that file. The high end is the sum, because one drive holding everything is always feasible if you are allowed that much capacity. If fits is false, mid is too small and every smaller capacity is also too small, so low becomes mid + 1. If fits is true, mid is a candidate and every larger capacity is also feasible, so high becomes mid.

How many steps? The numeric range has width S, the sum of the file sizes. Halving it takes log S steps. Each step scans every file once. Time is O(n log S). Extra space is constant. This is the complexity to say. Do not say "log n" unless n is the thing you are halving. Here n is the length of the scan inside the test.

How to tell the two settings apart

Ask what you are indexing. If the midpoint is an index into a sorted array, you are in the classic setting, and the comparison reads array[mid]. If the midpoint is a candidate answer, you are searching on the answer, and the comparison is a helper function you could have brute-forced. The helper must be monotonic. Test that claim on a tiny input before you code the loop: check a clearly-too-small value, a clearly-large value, and one in between. If the booleans are not a single flip from false to true, stop. Binary search will return a number, and the number will be nonsense.

Arrays and hashing do not need this monotonic story. If you wanted "have I seen this value," a map is the honest tool. Binary search is the wrong boast there, even if the final code is short.

Pitfalls and practice

Off-by-one errors are the tax on this pattern. Pick a loop shape and stick to it. The shape on this page is while left < right with a half-open range, which never checks a middle element twice and always shrinks the range. A shape that uses while left <= right must move left to mid + 1 and right to mid - 1, or it can spin forever when mid does not change. Infinite loops in an interview are usually this bug. The common mistakes page lists it next to other boundary errors.

Practice by rewriting first_at_least from memory, then changing it to return the last index whose value is at most the target. The invariant flips, and you should rewrite the invariant rather than poke operators until the asserts pass. Then change min_drive_capacity so files may be placed on any drive, not only in order. The helper's scan is no longer a single running total. Say whether monotonicity survives. It does, because a larger capacity still cannot make a previously possible packing impossible, but the helper itself gets harder. Knowing that the search is the easy half, and the feasibility test is the real problem, is the insight worth keeping for the four-week plan.