First and Last Position in Sorted Array

Find First and Last Position of Element in Sorted Array is the problem that teaches you binary search is not just for finding a match — it can find a boundary. The trick is to search for an edge instead of a value.

The slow way first

A plain linear scan finds both ends in O(n): walk left to right, note the first index equal to the target and the last one. That works, but the problem explicitly asks for O(log n), so a single pass over every element is off the table for a large array.

The question to ask: the array is sorted, so all the matching values sit in one contiguous block. Can I jump straight to the edges of that block instead of walking to them? Binary search can — if we teach it to hunt for a boundary rather than a single value.

The idea: search for the two edges

Equal values form a solid run. The first position is the left edge of that run; the last position is the right edge. We find each edge with a binary search called lowerBound:

• lowerBound(t) returns the first index whose value is >= t.
• lowerBound(target) lands on the left edge — the first index that is at least the target.
• lowerBound(target + 1) lands one step past the right edge — the first index strictly greater than the target. So the last position is that result minus one.

The key insight: a lowerBound that moves hi on >= (instead of stopping on ==) never settles on a random match in the middle — it keeps sliding toward the leftmost one. Reusing it with target + 1 gives the right edge for free.

Walk through it

Step through the animation. First lowerBound(3) runs: mid keeps landing on a 3 (still >= 3), so hi slides left until lo meets hi at index 1 — the first position. Then the same search runs for 4: every value < 4 pushes lo right and every value >= 4 pulls hi left, until they meet at index 4. Subtract one and the last position is 3.

Pseudocode

lowerBound(t):                       # first index with value >= t
    lo, hi = 0, n
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] >= t:
            hi = mid                 # answer is here or to the left
        else:
            lo = mid + 1             # answer is strictly to the right
    return lo
 
first = lowerBound(target)
upper = lowerBound(target + 1)
if first == n or nums[first] != target:
    return [-1, -1]                  # target never appears
return [first, upper - 1]

The Python solution

def search_range(nums, target):
    def lower_bound(t):
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] >= t:
                hi = mid
            else:
                lo = mid + 1
        return lo
 
    first = lower_bound(target)
    upper = lower_bound(target + 1)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    return [first, upper - 1]

• lower_bound(t) is the reusable boundary search: it returns the first index whose value is at least t.
• The window is half-open — hi starts at len(nums), so the search can legally point one past the last cell when every value is smaller than t.
• if nums[mid] >= t: hi = mid keeps a candidate in play and shrinks the window from the right, sliding toward the leftmost qualifying index.
• first = lower_bound(target) is the left edge; upper = lower_bound(target + 1) is one past the right edge.
• The guard first == len(nums) or nums[first] != target catches the case where the target is absent — then we return [-1, -1].
• Otherwise the answer is [first, upper - 1]: the right edge is always one less than where target + 1 would begin.

Complexity

Each lowerBound halves the search window every iteration, so it is O(log n); running it twice is still O(log n). We use only a handful of index variables, so the extra space is O(1).

When this pattern shows up

Practice