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

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

思路

题意就是，给定一个target，找到有序数组中target出现的首尾位置。
因为数组是有序的所以十有八九二分法没跑了(要有看到有序数组就想到二分法这个条件反射)。稍加分析可知，为了寻找target出现的首尾位置， 我们只需要两次二分法即可解决本题。第一次找到的是第一个target，第二次找到最后一个target。

• 第一次二分法为了找到第一个target，当target == nums[mid]时要令high = mid - 1然后进入下一次循环；
• 第二次二分法为了找到最后一个target，当target == nums[mid]时要令low = mid + 1然后进入下一次循环。

两次二分法时间复杂度同样为O(logn)，空间复杂度O(1)

改进

上面的算法在第二次二分查找时的初始范围为整个数组，这显然是有改进空间的的，因为在第一次搜索时已经找到了第一个target的位置(记为first)， 那么为了查找到最后一个target的位置(记为last)，我们只需要查找first及之后的位置就你可以了。
再仔细分析一下第一次二分的过程我们可以再缩小第二次二分的初始范围。第一次二分时:

• 当target < nums[mid]时，那么last一定在mid的前面(last < mid)；
• 当target == nums[mid]时，那么last一定在mid的后面(last >= mid)；

所以我们在第一次二分时记录last的下界(last_lower_bound)和上界(记为last_upper_bound)，第二次二分时初始范围即可缩小到[last_lower_bound, last_upper_bound]。 相对于改进前，这会缩短第二次二分的时间。

C++

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int len = nums.size();
        vector<int>res{-1, -1};
        if(len == 0) return res;
        
        // 第一次二分
        int low = 0, mid, high = len - 1;
        while(low <= high){
            mid = low + (high - low) / 2;
            if(target <= nums[mid]) high = mid - 1;
            else low  = mid + 1;
        } // low = high + 1
        // low == len或者nums[low]!=target说明没找到target
        if(low >= len || nums[low] != target) return res;
        res[0] = low; // 此时的low即第一个target的位置
        
        // 第二次二分
        low = 0;
        high = len - 1;
        while(low <= high){
            mid = low + (high - low) / 2;
            if(target >= nums[mid]) low = mid + 1;
            else high = mid - 1;
        }
        res[1] = high;
        return res;
        
    }
};

改进

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int len = nums.size();
        if(len == 0) return vector<int>{-1, -1};
        vector<int>res{-1, -1};
        int low = 0, mid, high = len - 1, last_lower_bound = 0, last_upper_bound = len - 1;
        while(low <= high){
            mid = low + (high - low) / 2;
            if(target <= nums[mid]) {
                high = mid - 1;
                if(target < nums[mid]) last_upper_bound = high;
                else last_lower_bound = mid;
            }
            else low  = mid + 1;
        } // low = high + 1
        
        
        if(low >= len || nums[low] != target) return res;
        res[0] = low;
        low = last_lower_bound;
        high = last_upper_bound;
        while(low <= high){
            mid = low + (high - low) / 2;
            if(target >= nums[mid]) low = mid + 1;
            else high = mid - 1;
        }
        res[1] = high;
        return res;
        
    }
};