# [34\. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

- 使用兩次 Binart Search，第一次先找 target 的左邊界，第二次找右邊界
- 找左邊界：`nums[mid] < target`，找右邊界：`nums[mid] <= target`
- 找不到 target 邊界條件：`right == n || nums[right] != target`

:::spoiler Solution

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;
    }
};

- 時間複雜度：$O(\log n)$
- 空間複雜度：$O(1)$
:::