Where a repeated value starts and ends

A sorted list may hold a value many times. Report the first and last positions where a target appears, or -1 -1 if it does not appear at all.

Worked example#

For [5, 7, 7, 8, 8, 8, 10] looking for 8: it appears at positions 3, 4 and 5, so the answer is 3 5.

Looking for 6 gives -1 -1.

The idea#

Plain binary search finds a position holding the target, and which one depends on where the halving happened to land. That is not enough here: you want the ends.

The fix is small and worth internalising. When you land on the target, do not stop. Write the position down, then keep searching on the side the edge you want is on:

• for the first occurrence, carry on to the left;
• for the last, carry on to the right.

The last position you wrote down before the search closes is the edge.

while low <= high:
    if nums[mid] == target:
        found = mid
        if looking for the first: high = mid - 1
        else:                     low = mid + 1
    elif nums[mid] < target: low = mid + 1
    else:                    high = mid - 1

Two runs, one per edge. Both are log n, so the whole thing is too.

Why not just walk outwards#

Finding one occurrence and then stepping left and right while the value matches is simple and correct. On [8, 8, 8, ..., 8] with a hundred thousand copies it walks the whole list, which turns a log n search into an n one. The whole reason to use binary search here is to not care how many copies there are.

What it is really doing#

"Keep going even after a hit" is the shape of every find the boundary binary search: the first value at least as large as the target, the last one below it, the leftmost position where a condition turns true. Once you have written it twice it stops feeling like a trick.

Constraints#

• 0 <= n <= 100000, sorted in increasing order