34. Find First and Last Position of Element in Sorted Array

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        int n = nums.size();
        vector<int> res(2, -1);

        int left = 0, right = n;

        // 第一次 binary search，目標在尋找左邊界
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            // 如果 nums[mid] 在 target 的左邊
            // 代表想找的值在右邊
            if (nums[mid] < target)
            {
                // 往右邊尋找
                left = mid + 1;
            }
            else
            {
                // 往左邊尋找
                right = mid;
            }
        }
        // 以 nums = [5,7,8,8,8,8] 來說
        // 這時候的 right 會等於 2
        // 右指標會不斷地往左尋找，尋找 target 的左邊界

        // 如果右指標走訪到數列尾端，或者是 nums[right] 不等於 target 的話
        if (right == n || nums[right] != target)
        {
            // return {-1, -1} 代表找不到
            return res;
        }

        // 儲存目標值的左邊界
        res[0] = right;

        // 將右指標重設為 n
        right = n;

        // 第二次 binary search
        while (left < right)
        {
            int mid = left + (right - left) / 2;

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

        // 儲存目標值的右邊界
        res[1] = right - 1;

        return res;
    }
};

• T: $O(\log n)$
• S: $O(1)$