Premium

First and Last Position

Basic Algorithms
≈ 2 min read

Duplicates turn the search into a boundary problem

In a sorted array, equal values stand next to one another. Therefore all occurrences of target form one continuous range. Its beginning can be found with lower bound, and its end with upper bound. 

static int[] firstAndLast(int[] values, int target) {
    int first = lowerBound(values, target);

    if (first == values.length || values[first] != target) {
        return new int[] {-1, -1};
    }

    int last = upperBound(values, target) - 1;
    return new int[] {first, last};
}

First, we find the first position whose value is not less than the target. If that position is outside the array or contains a different value, then target is absent. Otherwise, the first index is already known.

Why upper bound is decreased by one

Upper bound points to the first position whose value is greater than the target. Therefore, the last occurrence of target is immediately before that boundary. That is why the expression upperBound(values, target) - 1 is used.

The complexity does not change

We run two binary searches, each taking O(log n). The total is still O(log n), because a constant number of logarithmic passes does not change the asymptotic complexity.

Expanding linearly to the left and right from one found match is usually a poor choice: if the whole array contains the same value, that extra step turns the solution into O(n).
Back Next