Link to Question

MEDIUM

Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example

Input:

nums = [5,7,7,8,8,10], target = 8

Output:

[3,4]

Explanation:
The target 8 appears from index 3 to 4.

---

Constraints

• 0 ≤ nums.length ≤ 10⁵
• -10⁹ ≤ nums[i] ≤ 10⁹
• nums is a non-decreasing array.
• -10⁹ ≤ target ≤ 10⁹

---

Solution: Binary Search

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

C++

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1, left = -1, right = -1;
        while(l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (l < nums.size() && nums[l] == target) left = l;
        else return {left, right};
        r = nums.size() - 1;
        while(l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > target) r = mid;
            else l = mid + 1;
        }
        if (nums[l] > target) l--;
        return {left, l};
    }
};