Sharing my C++ solution using two binary searches


  • 0
    T
    class Solution {
    private:
        int getStartAfterRotation(vector<int>& nums)
        {
            int left = 0;
            int right = nums.size()-1;
            int middle;
            while(left<right)
            {
                middle = (left+right)/2;
                if(nums[middle]>nums[right])
                    left = middle+1;
                else
                    right = middle;
            }
            
            return left;
        }
        
        int binarySearch(vector<int>& nums, int target, int left, int right)
        {
            int n = nums.size();
            
            if(left>right)
                return -1;
            else
            {
                int middle = (left+right)/2;
                if(nums[middle%n]==target)
                    return middle%n;
                else if(nums[middle%n]>target)
                    return binarySearch(nums, target, left, middle-1);
                else
                    return binarySearch(nums, target, middle+1, right);
            }
        }
        
    public:
        int search(vector<int>& nums, int target) {
            int start = getStartAfterRotation(nums);
            int end = start + nums.size()-1;
            return binarySearch(nums, target, start, end);
        }
    };

Log in to reply
 

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