034 - Search for a Range

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].

Hide Tags

Array Binary Search

Hide Similar Problems

(M) Search Insert Position

 

二分查找，只是对于mid，要左右查找相等的值的范围罢了。

 

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> rst(2, -1);
        int sz=nums.size();
        if(sz)
            qs(nums, 0, sz-1, target, rst);
        return rst;
    }
   
    void qs(vector<int>& nums, int start, int end, int tgt, vector<int>& rst)
    {
        if(start>end)
            return;

        int mid = (start+end)/2;
        int mid_s=mid, mid_e=mid, mss=nums[mid_s], mee=nums[mid_e];
        while(mid_e<=end && (nums[mid_e]==mee))
            mid_e++;
        while(mid_s>=start && (nums[mid_s]==mss))
            mid_s--;
        if(mss==tgt)
        {
            rst[0] = mid_s+1, rst[1] = mid_e-1;
            return;
        }

        if(tgt<mss)
            qs(nums, start, mid_s, tgt, rst);
        else
            qs(nums, mid_e, end, tgt, rst);
       
        return;
    }
};

12 ms.