Find First and Last

Using lower bound and upper bound together, you can find the first and last occurrence of a value.

Problem: Find the starting and ending position of a target in a sorted array.

Solution:

function searchRange(arr, target):
    first = lowerBound(arr, target)

    if first == arr.length or arr[first] != target:
        return [-1, -1]

    last = upperBound(arr, target) - 1
    return [first, last]

Example: Find range of $5$ in $[1, 3, 5, 5, 5, 7, 9]$.

• Lower bound of $5$: index $2$.
• Upper bound of $5$: index $5$.
• Range: $[2, 4]$.

Time: $O(\log n)$ for two binary searches.