Implementing Binary Search Correctly

Fix the interval convention before you write the loop. The classic closed form starts with low at zero and high at the length minus one, and the loop runs while low is less than or equal to high. Inside, compute the midpoint as low plus half of the high minus low, which avoids overflow in fixed width languages. Compare, and then either move low to mid plus one or high to mid minus one. Getting the midpoint as the average of low and high is also correct, but it is the source of overflow bugs in other languages.

def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

data = [1, 3, 5, 7, 9, 11]
print(binary_search(data, 7))
print(binary_search(data, 4))

The outputs are 3 and minus one. The target 7 sits at index three, and 4 is not present, so the search exhausts the interval and reports failure.

The mechanism is the halving. Each comparison discards half of the remaining candidates because the array is sorted, so after k steps the interval has shrunk by a factor of two to the power k and the search finishes in logarithmically many steps.

The trade-off to name is that binary search only works on ordered data, and that the ordering has to be by the key you are comparing. The classic mistakes are mixing conventions, such as starting high at the length and then also using the closed form, and forgetting to move the wrong pointer, which makes the search loop forever. Another subtle bug is returning the first match when duplicates exist, because the binary search has no idea which occurrence it landed on. In an interview, stating the interval convention out loud before you type is what prevents these, and it is the habit the interviewer is really checking.

Use the half open interval form and do not stop when you find a match. Instead, keep searching to the left whenever you hit an equal value, so the search converges on the leftmost occurrence. This variant is usually called a lower bound.

def lower_bound(values, target):
    low, high = 0, len(values)
    while low < high:
        mid = low + (high - low) // 2
        if values[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low


data = [1, 3, 3, 3, 5, 7]
print(lower_bound(data, 3))
print(lower_bound(data, 4))

The outputs are 1 and 4. The first call finds the first index holding 3, which is index one. The second finds the first index holding a value of at least 4, which is index four where the 5 sits.

The mechanism is the interval convention. The range is half open, low to high exclusive, and the loop condition is low less than high rather than less than or equal. That means the loop can end with low equal to high, and low is then the answer without needing a special case for not found. When the target is absent, the function returns the position where it would have been inserted, which is the useful property that makes this the building block for everything else in this family.

The trade-off to name is that this version never reports failure. Callers that need to distinguish present from absent must compare the returned index against the length and check the value, which is exactly what the search range function does. The half open convention is also the reason this style is easier to reason about: there is no possibility of an empty interval and no off by one at the end, because the answer is simply where low and high meet.

Build both boundaries from the lower bound idea. The first position is the lower bound of the target, and the last position is the lower bound of the target plus one, minus one. If the lower bound of the target is out of range or does not actually hold the target, the target is absent.

def search_range(values, target):
    def lower_bound(t):
        low, high = 0, len(values)
        while low < high:
            mid = low + (high - low) // 2
            if values[mid] < t:
                low = mid + 1
            else:
                high = mid
        return low

    start = lower_bound(target)
    if start == len(values) or values[start] != target:
        return [-1, -1]
    end = lower_bound(target + 1) - 1
    return [start, end]


data = [1, 3, 3, 3, 5, 7]
print(search_range(data, 3))
print(search_range(data, 4))

The outputs are 1, 3 and minus one, minus one. The three occurrences of 3 sit at indices one, two and three, and the target 4 is not present at all.

The mechanism is that the lower bound of target plus one is the first position holding a value strictly greater than the target. Because the array is sorted, everything between the lower bound of the target and that position is equal to the target, so the last occurrence is exactly one before it. Both searches are logarithmic, so the whole thing is logarithmic in time and constant in space.

The trade-off to name is that this is two searches rather than one, so it does roughly twice the comparisons of a plain search. If you need the range often on the same array, it is worth precomputing a map from value to its first and last positions, which trades memory for constant time lookups. A single pass that finds one match and then scans outwards also works, but that scan is linear in the number of duplicates, which is why the two-boundary approach is the better one when duplicates are common.