First and Last Position in a Sorted Array

Run two binary searches. The first one looks for the leftmost occurrence: when it finds a match it keeps going to the left. The second looks for the rightmost occurrence: when it finds a match it keeps going to the right. If the first search finds nothing, the value is absent and both positions are minus one.

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


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

The outputs are 3, 3 and minus one, minus one. The three occurrences of 3 sit at indices one, two and three, so the range is from one to three. The target 4 is not in the array, so both positions stay at minus one.

The mechanism is that a binary search which stops at the first match it happens to land on cannot tell you whether it landed on the first or the fifth copy. Continuing the search in the appropriate direction resolves that. The asymmetry between the two loops is the whole trick: one keeps high just below the midpoint, the other keeps low just above it.

The trade-off to name is that this does two searches where one would do, so it costs roughly twice the comparisons. The alternative is the lower bound formulation, where the first position is the lower bound of the target and the last is the lower bound of the target plus one minus one, which is the same amount of work but with a tidier structure and no special case for not found. The brute force alternative scans the array for the first and last match and is linear, and it is the right answer when the array is not actually sorted.

Instead of stopping at a match, treat an equal value as a candidate answer and keep moving right. Whenever the midpoint is less than or equal to the target, the midpoint is either the answer or lies before it, so the search continues to the right half and the last match found wins.

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


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

The outputs are 3 and minus one. The three copies of 3 sit at indices one, two and three, and the last one is at index three. The target 4 falls between 3 and 5, so nothing is ever recorded and the result stays at minus one.

The mechanism is that the search never gives up a region that might contain a later match. Because the array is sorted, any value greater than the target means everything to the right is greater too, so the interval can be cut there. Any value less than or equal to the target means the answer, if it exists, is at the midpoint or to its right, so the interval is cut on the left and the candidate is remembered.

The trade-off to name is that the loop condition of less than or equal rather than strictly less is what makes this work. Using a strict comparison would terminate at the first value greater than the target, and comparing with less than only would find the first occurrence instead. This version also reports minus one rather than raising an error when the value is absent, which is a contract worth stating. If you need the count of occurrences as well, the answer is the lower bound of the target plus one minus the lower bound of the target, using two logarithmic searches.