Binary search when the target is not there

Plain binary search finds an exact value or reports failure. Most real uses want something slightly different, and the differences are all in two lines.

The boundary versions

Lower bound: the first position where the value could be inserted keeping order, which is the first element not less than the target.

def lower_bound(nums, target):
    lo, hi = 0, len(nums)          # hi is one past the end
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

Upper bound is the same with <= instead of <, and gives the first element strictly greater.

Between them they answer the questions that come up in practice:

Note this loop never returns from the middle, hi starts past the end, and the condition is lo < hi. Those three choices together are what make it terminate correctly on every input, including empty ones.

Getting the loop right

Two bugs account for nearly all failures.

mid = (lo + hi) // 2         # overflows in C++ and Java for large values
mid = lo + (hi - lo) // 2    # safe everywhere

And the infinite loop: if the window can fail to shrink, it never ends. Every branch must either raise lo past mid or lower hi to mid, and if one branch leaves both unchanged the loop spins.

Searching the answer, not the array

The most useful variant searches a range of possible answers, and it is what interviewers are usually testing.

Ship packages within D days, choosing the smallest daily capacity:

def min_capacity(weights, days):
    def enough(cap):
        needed, load = 1, 0
        for w in weights:
            if load + w > cap:
                needed += 1
                load = 0
            load += w
        return needed <= days

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

Nothing is sorted and there is no array to search. What makes it work is that the answer is monotonic: if a capacity is enough then every larger one is too. That property, and not sortedness, is the real requirement for binary search.

The recognition to carry: "smallest value such that a condition holds" plus a condition that stays true once true means binary search on the answer.