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

## 1.問題

* 給予一個升冪排序過的array, 找出首次出現及最後出現的位置
* 時間複雜度須為O(log n)
* 如果array中沒有target, 則回傳 \[-1, -1]

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LS1yqpjjXHJ6iYM2tML%2F-LS1zUrZ-y8JfskCYdoC%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-11-24%20%E4%B8%8A%E5%8D%887.52.51.png?alt=media\&token=c5dd5a0c-e50f-4d94-9648-4f99b2f05494)

## 2.想法 

* O(log n)暗示使用binary search:
  * 找出target的left bound, 並找出target + 1的left bound -1 

## 3.程式碼 

```
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if (nums.size() == 0) {
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
        int first = getLowerBound(nums, target, 0, nums.size() - 1); 
        int second = getLowerBound(nums, target + 1, 0, nums.size() - 1) - 1;
        if (first < nums.size() && nums[first] == target) {
            res.push_back(first);
            res.push_back(second);
        } else {
            res.push_back(-1);
            res.push_back(-1);
        }
        return res;
    }
private:
    int getLowerBound(vector<int>& nums, int target, int left, int right)
    {
        if (left > right) {
            return left;
        }
        
        int mid = (left + right) / 2;
        if (nums[mid] < target) {
            return getLowerBound(nums, target, mid + 1, right);
        } else {
            return getLowerBound(nums, target, left, mid - 1);
        }
    }
};
```