"Rotated binary search" way to solve it using C++.


  • 0
    X

    Since the array is rotated, in my binary search, I rotate my (left, right, mid) pointers accordingly, and finally, I got the solution just as the normal binary search.

     bool search(vector<int>& nums, int target) {
        if(!nums.size()) return false;
        
        int len=nums.size();
        int index=0;
        for(int i=1; i<len; i++)
        {
            if(nums[i]<nums[i-1])
            {
                index=i; //find the rotate position
                break;
            }
        }
        
        int left=index;
        int right=(index+len-1)%len;
        int count=len;//the "rotate size" between left and right
        while(left != right)
        {
            int mid = (left + count/2)%len;
            if(nums[mid] ==target) 
                return true;
            if(nums[mid]<target)
            {
                left = (mid+1)%len;
                count/=2;
            }
            else
            {
                right=mid;
                count = (int)ceil(count/2);
            }
        }
        return nums[left]==target;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.