Find First and Last Position of Element in Sorted Array

Intuitionduplicates require a boundary, not an ordinary match

A normal binary search can stop as soon as it sees target because any occurrence is acceptable. This problem asks for a specific occurrence: the leftmost target and the rightmost target. When nums[mid] equals target, the answer may still lie farther left or farther right, so equality cannot end the search.

For the first position, treat target as a dividing line. Values smaller than target must stay to the left, while values equal to or greater than target may still contain the first occurrence, so you keep searching left after a match. For the last position, reverse that decision: values greater than target move right, while values less than or equal to target may still contain the last occurrence.

Approachturn equality into a directional decision

1. 1Set first and last to -1 before searching, because an absent target must produce two sentinel values rather than an index left over from an earlier comparison.
2. 2Run a binary search for the first position using the condition nums[mid] >= target. Move right to mid - 1 when the condition holds, because mid could be the first target but every position at or after it cannot be an earlier answer.
3. 3Record first = mid whenever nums[mid] == target, because the current midpoint is a valid occurrence even though the search must continue left to discover whether an earlier one exists.
4. 4If nums[mid] < target, move left to mid + 1, because every position through mid is too small and cannot contain target.
5. 5If first is still -1 after the first search, return {-1, -1} immediately, because the target never appeared and a second boundary search would have no valid occurrence to report.
6. 6Reset the bounds and run a second binary search using nums[mid] <= target. Move left to mid + 1 when the condition holds, because mid could be the last target but every position at or before it cannot be a later answer.
7. 7Record last = mid whenever nums[mid] == target, and move left when nums[mid] > target; this preserves the rightmost candidate while discarding values that are too large. Return {first, last} after the second search because both recorded indices are now boundaries.

Complexitytwo logarithmic searches still make one logarithmic algorithm

Annotated solutionC++ · two boundary searches · explicit invariants

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0;
        int right = static_cast<int>(nums.size()) - 1;
        int first = -1;
        int last = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

            if (nums[mid] == target) {
                first = mid;
            }
        }

        if (first == -1) {
            return {-1, -1};
        }

        left = 0;
        right = static_cast<int>(nums.size()) - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }

            if (nums[mid] == target) {
                last = mid;
            }
        }

        return {first, last};
    }
};

The order inside each loop matters. The comparison moves the search boundary, while the equality check saves the current midpoint before that candidate disappears from the next interval. In the first loop, right moves left on equality; in the second, left moves right on equality. Those opposite movements are the entire difference between first and last.

The library-bound alternativeshorter code, with the boundary definitions delegated to the standard library

A competent alternative is to use lower_bound for the first position and upper_bound for the position immediately after the last one. This is an optimisation in code length, not in asymptotic performance: both library searches are logarithmic and the extra space remains constant. It buys a compact implementation, while the explicit loops make the equality decisions easier to inspect when you are learning or debugging binary search.

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        auto firstIt = lower_bound(nums.begin(), nums.end(), target);

        if (firstIt == nums.end() || *firstIt != target) {
            return {-1, -1};
        }

        auto afterLastIt = upper_bound(nums.begin(), nums.end(), target);
        int first = static_cast<int>(firstIt - nums.begin());
        int last = static_cast<int>(afterLastIt - nums.begin()) - 1;

        return {first, last};
    }
};

lower_bound returns the first iterator whose value is not less than target, so it lands on the first target if one exists. upper_bound returns the first iterator whose value is greater than target, so subtracting one gives the last target. The explicit existence check is essential because lower_bound can legally return end when every value is smaller than target.

Common mistakesboundary searches fail in specific, repeatable ways