34. Search for a Range 搜索一个范围

Given an array of integers 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].

For example, Given [5, 7, 7, 8, 8, 10] and target value 8,

return [3, 4].

解法1

这道题让我们在一个有序数组中查找与输入target相同的起始位置和结束位置,限定时间复杂度为O(logn),这个是典型的二分查找时间复杂度.这道题我们先采用二分法找到一个与target相同的index,再想index的左边和右边搜索.

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int index = search(nums,0,nums.size()-1,target);
        if (index==-1) return {-1,-1};
        int left = index,right = index;
        while (left>0&&nums[left-1]==nums[index]) left--;
        while (right<nums.size()-1&&nums[right+1]==nums[index]) right++;
        return {left,right};
    }
    
    int search(vector<int>&nums,int left,int right,int target){
        if (left>right) return -1;
        int mid = (left+right)/2;
        if (nums[mid]==target) return mid;
        else if (nums[mid]<target) return search(nums,mid+1,right,target);
        else return search(nums,left,mid-1,target);
    }
};

解法2

上面的解法 当数组中的元素都相同的时候,相当从中间遍历到两边为O(n).下面可以用一个二分法查左边坐标,一个二分法查右边的坐标.

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()-1;
        //right向左偏移
        while (left<right) {
            int mid = (left+right)/2;
            if (nums[mid]<target) left=mid+1;
            else right=mid;
        }
        if (nums[right] != target) return res;
        res[0] = right;
        //如果输入[1],1.right=nums.size()出错
        right = nums.size();
        //left向右偏移
        while (left<right) {
            int mid = (left+right)/2;
            if (nums[mid]<=target) left=mid+1;
            else right=mid;
        }
        res[1]=left-1;
        return res;
    }
 
comments powered by Disqus