康瑞部落

Search for a Range

Given a sorted array of integers, 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].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

解题思路：

这道题的题意是找到排序数组中目标值的下标范围，这个数组可能会有相同的元素。

题目要求时间复杂度在O(logn)。3次二分查找。第一次找到一个值为target的下标k，第二次找到0~k中值为target的最小下标，第三次找到k~len-1中值为target的最大下标。每次的时间复杂度为O（logn）。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result({-1, -1});
        
        int start=0, end=nums.size()-1;
        int middle;
        //找到第一个
        while(start<=end){
            middle=(start+end)/2;
            if(nums[middle]==target){
                result[0]=result[1]=middle;
                break;
            }else if(nums[middle]>target){
                end=middle-1;
            }else{
                start=middle+1;
            }
        }
        
        if(result[0]!=-1){
            //找到最小的那个下标
            start=0;
            end=result[0]-1;
            while(start<=end){
                middle=(start+end)/2;
                if(nums[middle]==target){
                    end=middle-1;
                    result[0]=middle;
                }else{
                    start=middle+1;
                }
            }
            //找到最大的那个下标
            start=result[1]+1;
            end=nums.size()-1;
            while(start<=end){
                middle=(start+end)/2;
                if(nums[middle]==target){
                    start=middle+1;
                    result[1]=middle;
                }else{
                    end=middle-1;
                }
            }
        }
        
        return result;
    }
};

二次刷题（2015-08-18）

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int len = nums.size();
        vector<int> result({-1, -1});
        int start = 0, end = len - 1;
        while(start <= end){
            int middle = (start + end) / 2;
            if(nums[middle] == target){
                result[0] = result[1] = middle;
                break;
            }else if(nums[middle] < target){
                start = middle + 1;
            }else{
                end = middle - 1;
            }
        }
        if(result[0]>=0){
            //找到左侧的
            start = 0;
            end = result[0]-1;
            while(start<=end){
                int middle = (start + end)/2;
                if(nums[middle] == target){
                    result[0] = middle;
                    end = middle - 1;
                }else{
                    start = middle + 1;
                }
            }
            
            //找到右侧的
            start = result[1] + 1;
            end = len - 1;
            while(start<=end){
                int middle = (start + end) / 2;
                if(nums[middle] == target){
                    result[1] = middle;
                    start = middle + 1;
                }else{
                    end = middle - 1;
                }
            }
        }
        return result;
    }
};