081 - Search in Rotated Sorted Array II

Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

Hide Tags

Array Binary Search

Hide Similar Problems

(H) Search in Rotated Sorted Array

 

在033的基础上加上了可以出现重复的值，

带来的问题是，begin/end 跟 mid的值可能一样，从而影响判断。

所以加两个处理，从mid分别向左右检查直到遇到不同的值，

这样就避免了上述情形，但是递归的条件里要加上等号。

复杂度上没有本质变化吧，但添加的处理可能会有增加，取决于多少个重复的值了。

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int sz = nums.size();
        if(sz)
            return (-1!=bsearch(nums, target, 0, sz-1));
        return false;
    }
   
   
    int bsearch(vector<int>& nums, int tgt, int begin, int end)
    {
        if(begin>end)
            return -1;
           
        if(tgt == nums[begin])
            return begin;
        if(tgt == nums[end])
            return end;
           
        int mid = (begin+end)/2;
        if(tgt == nums[mid])
            return mid;
       
        int leftend = mid;
        while((leftend>begin)&&(nums[leftend]==nums[mid]))
            leftend--;

        int rightbegin = mid;
        while((rightbegin<end)&&(nums[rightbegin]==nums[mid]))
            rightbegin++;

        if(((nums[begin]<nums[leftend])&&((tgt>nums[begin])&&(tgt<=nums[leftend])))
            || ((nums[begin]>nums[leftend])&&((tgt<=nums[leftend])||(tgt>nums[begin]))))
            return bsearch(nums, tgt, begin+1, leftend);

        else if(((nums[rightbegin]<nums[end])&&((tgt>=nums[rightbegin])&&(tgt<nums[end])))
            || ((nums[rightbegin]>nums[end])&&((tgt>=nums[rightbegin])||(tgt<nums[end]))))
            return bsearch(nums, tgt, rightbegin, end-1);
       
        else
            return -1;
    }

};

8 ms.