> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/34.-find-first-and-last-position-of-element-in-sorted-array.md).

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

## 1.問題

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

![](/files/-LS1zUrZ-y8JfskCYdoC)

## 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);
        }
    }
};
```