# 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个判断分支更加平衡以及快速


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET 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?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.