Find First and Last Position of Element in Sorted Array

How it works

Most programming languages provide built-in functions for binary search that find lower and upper bounds. These functions are optimized and well-tested, making them a practical choice when available. The lower bound gives the first occurrence, and the upper bound (minus one) gives the last occurrence.

Steps

1. Use the language's built-in lower-bound function to find the first position where the target could be inserted.
2. If this position is out of bounds or doesn't contain the target, return [-1, -1].
3. Use the upper-bound function to find the position just after the last occurrence.
4. Return [lower_bound, upper_bound - 1].

Complexity

• Time complexity: O(log n)
• Space complexity: O(1)

Things to watch for

Returning Early When Target Is Found

Standard binary search returns immediately upon finding the target, but this gives an arbitrary occurrence, not the first or last. You must continue searching (leftward for first, rightward for last) even after finding a match to locate the boundary positions.

Not Handling the Target-Not-Found Case

After performing binary search for the first occurrence, you must verify that the found index actually contains the target. If the target does not exist in the array, the binary search returns an insertion point, not a valid position. Always check bounds and value equality before returning.

Off-by-One Errors in Boundary Calculation

When using lower-bound and upper-bound style searches, the upper bound points to one past the last occurrence. Forgetting to subtract 1 when computing the end position, or using incorrect loop conditions (l <= r vs l < r), leads to wrong indices or infinite loops.

from typing import List
from bisect import bisect
import bisect

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = bisect.bisect_left(nums, target)
        if left >= len(nums) or nums[left] != target:
            return [-1, -1]

        right = bisect.bisect_right(nums, target) - 1
        return [left, right]

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        if (left == nums.size() || nums[left] != target) {
            return {-1, -1};
        }

        int right = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - 1;
        return {left, right};
    }
};