Find First and Last Position of Element in Sorted Array

Two lower-bound binary searches: the first index holding a value >= target, and the first index holding a value > target. The run of target sits between them.

The idea

In a sorted array all copies of the target sit next to each other. The first copy is the first index whose value is >= target. The position just after the last copy is the first index whose value is > target, which for integers is the first value >= target + 1. One lower-bound search answers each question in O(log n), and it never stops early on a match: it keeps narrowing to the boundary.

Code

public int[] SearchRange(int[] nums, int target) {
    int first = LowerBound(nums, target);
    if (first == nums.Length || nums[first] != target) return new[] { -1, -1 };
    int last = LowerBound(nums, target + 1) - 1; // first value > target, minus one
    return new[] { first, last };
}

// first index i with nums[i] >= x (nums.Length if there is none)
static int LowerBound(int[] nums, int x) {
    int lo = 0, hi = nums.Length; // search the half-open window [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < x) lo = mid + 1; // mid and everything left of it is too small
        else hi = mid; // mid could be the answer, keep it
    }
    return lo;
}

Tips

• A plain binary search stops at whichever copy it hits first. Lower bound keeps searching left after a match (hi = mid), so it lands on the boundary.
• The window is half-open, [lo, hi): hi = nums.Length means "past the end", the answer when every value is smaller than x.
• Try target 9 with the default array: the first search stops at index 5 (value 10), which is not 9, so the answer is [-1, -1].

In the .NET library

Array.BinarySearch returns some matching index, not necessarily the first, so it cannot replace LowerBound here. Use target + 1 only when target < int.MaxValue, or write a separate UpperBound with nums[mid] <= x.