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

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

## problem description

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

Your algorithm's runtime complexity must be in the order of *O*(log *n*).

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

**Example 1:**

```
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
```

**Example 2:**

```
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
```

## algorithm thought

找到第一个target和最后一个target，需要时间复杂度是O(lgn)。其实就是二分查找，但是不是单纯的二分查找。需要找到第一个和最后一个。这其实很像stl函数中的lower\_bound和up\_bound。但是upper\_bound是找到一个不是target的值。我们只需要将upper\_bound最后的索引减一就行了。

之前我一直搞不清这几个二分查找的本质区别和如何去写。这个我总结出了规律，对于lower\_bound，要找到第一个target，在mid>=target的时候，将right=mid，最后一次查找的时候，right就会是第一个target。左开右闭表示法，最后当left和right差1的时候，mid肯定等于left，所以最后left会赋值给right+1。left和right会在第一个target处重合。

对于up\_bound同理，只要将mid>=target改为mid>target即可。这样就会在刚好大于target的地方重合。我理解这两个二分查找也是用了很久时间，看文字肯定会有很多疑惑，可以反复看看代码，自习推敲。

## code

```cpp
//upper_bound
void uppper_bound(int l,int r,int x){
      while(l<r）{
        int mid=(r-l)/2;
        if(a[mid]>x) r=mid;
        else  l=mid+1;
    }
}

//low_bound
void lower_bound(int l,int r,int x){
      while(l<r）{
        int mid=(r-l)/2;
        if(a[mid]>=x) r=mid;
        else  l=mid+1;
    }
}

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

## algorithm analysis

都是二分查找时间复杂度是O(lgn)，stl中的二分查找也是直接用low\_bound实现的，low\_bound在二分查找中只有两个判断分支，会比传统的3个判断分支更加平衡以及快速