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

binary_search&&low_bound&&up_bound

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

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