[leetcode] 34 find first and las

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]

有序数组中查找target 的 首次 和 最后一次出现下标

这题我用的方法很蠢， 就是 二分找出target, 然后O(n) 的往前，往后 找 first 和 last. 如果target有大量重复, 速度就会很慢， 但是这题 case 比较友好。。。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        
        vector<int> ans;
        
        if(nums.empty()) return vector<int>{-1,-1};
        //step 1 : binary search target
        
        int begin = 0, end = nums.size()-1,mid = 0;
        
        while(begin +1 < end){
            mid = begin + (end - begin)/2;
            if(nums[mid] > target)
                end  = mid;
            else if(nums[mid] < target)
                begin = mid;
            else
                break;
        }
        if(nums[begin]!= target && nums[mid] != target && nums[end] != target )
            return vector<int>{-1,-1};
        
        // step 2 : find first position
        int initiate = 0;
        if(nums[begin] == target) 
            initiate = begin;
        else 
            initiate = nums[mid] == target? mid: end;
        // 越界情况
        while(initiate >=0 && nums[initiate]== target)
            initiate--;
        ans.push_back(++initiate);
        // step3: find last position
        
        //越界情况
         while(nums[initiate]== target && initiate <= nums.size()-1 )
             initiate++;
        ans.push_back(initiate-1);
        
        return ans; 
        
    }
};

image.png

我们显然不能面向case 编程， 该优化的还是要优化。
这里只需要对 binary search 做一些小的修改就好了

        while(begin+1 < end){
            mid = begin + (end- begin) /2;
            if(nums[mid] >= target)
                end = mid;
            else if(nums[mid] < target)
                begin = mid;       
        }

在find first position 的过程中，mid等于target 的时候， end 左移。
类似[1,2,3,3,3,3,3,3] --> [1,2,3,3,3]-->[1,2,3] 这样的过程

这样一般情况下,最后退出情况就是
begin < target, end= target,并且 begin, end 相邻。
比如[1,2,3,3,3,3,4] -->[2,3]

但是如果数组类似[2,2,2]的情况，begin 也有可能是first position
所以 我们这里 优先选择begin作为下标.

        end = nums[begin] == target? begin: end;
        ans.push_back(end );

find last postion 就是对[first element of target, ........, nums.size()-1]这个数组进行二分。

这是 数组内所有元素都大于等于target
所以 只要考虑将 begin 不断右移 ,
类似[2,2,2,2,2,3] --> [2,2,3]-->[2,3] 这种情况

使得最后退出条件是begin= target, end> target,begin,end相邻
同理，这里也要考虑[2,2,2]这种数组，

        begin = nums[end] == target? end:begin;
        ans.push_back(begin);

所以退出find last position 循环后， 优先选择end 作为 last element of target的下标。

完整代码如下。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        int begin = 0, end = nums.size()-1,mid= 0;
        
        // find first
        // 
        while(begin+1 < end){
            mid = begin + (end- begin) /2;
            if(nums[mid] >= target)
                end = mid;
            else if(nums[mid] < target)
                begin = mid;       
        }
        if(  nums.empty() || (nums[begin] != target && nums[end] != target) )
            return vector<int>{-1,-1};
        
        end = nums[begin] == target? begin: end;
        ans.push_back(end );
        
        // find last
        begin = end;
        end = nums.size()-1;
        while(begin +1<end){
            mid= begin + (end-begin)/2;
            if(nums[mid]> target)
                end = mid;
            else
                begin = mid;
        }
        
        begin = nums[end] == target? end:begin;
        ans.push_back(begin);
        
        return ans;
             
    }
};

image.png