81. Search in Rotated Sorted Array II (Array; Divide-and-Conquer)

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.

思路：此时可能存在nums[start]=nums[end]或者nums[start]=nums[mid]或者nums[mid]=nums[end]。所以无法用原来方法判断是否正序、右侧rotate、或者左侧rotate。解决方法是，当碰到nums[start]=nums[end]的情况时，end-1，寻找不同元素再进行二分法。

class Solution {

public:

    bool search(vector<int>& nums, int target) {

        return binarySearch(nums,,nums.size()-, target);

    }

    bool binarySearch(vector<int>& nums, int start, int end, int target){

        if(start==end){

            if(nums[start]==target) return true;

            else return false;

        }

        if(nums[start]==nums[end]) return binarySearch(nums,start,end-,target); //ignore duplicate

        int mid = start+ ((end-start)>>);

        //正序

        if(nums[mid]>=nums[start] && nums[mid]<nums[end]){ //mid可能=start，所以>=

            if(target <= nums[mid]) return binarySearch(nums,start,mid,target); //mid肯定<end，所以至少舍弃了一个

            else return binarySearch(nums,mid+,end,target); //mid+1,至少舍弃了一个

        }

        //右侧rotate

        else if(nums[mid]>=nums[start] && nums[mid]>=nums[end]){

            if(target>=nums[start] && target<=nums[mid]) return binarySearch(nums,start,mid,target);

            else return binarySearch(nums,mid+,end,target);

        }

        //左侧rotate

        else{

            if(target>=nums[start] || target<=nums[mid]) return binarySearch(nums,start,mid,target);

            else return binarySearch(nums,mid+,end,target);

        }

    }

};

巴特西

81. Search in Rotated Sorted Array II (Array; Divide-and-Conquer)

最新文章

热门文章