C++ 4ms solution, based on findMin and binarySearch with explaination


  • 1
    J

    Firstly, the leetcode problem "Find Minimum in Rotated Sorted Array" solution here

    When we found the min index, we call binarySearch(0, index-1) and binarySearch(index, nums.size() -1), and return the bigger one. here is the code

    class Solution {
        int findMin(vector<int>& nums, int l, int r){
        	if(nums.size() == 1)
                return 0;
        	if (l < 0 || r < 0 || l >= nums.size() || r >= nums.size())
        		return -1;
        	int mid = (l + r) / 2;
        	if (l <= r){
        		if (mid == 0)
        			return nums[mid] > nums[mid + 1] ? mid + 1 : -1;
        		if (mid == nums.size() - 1)
        			return nums[mid] < nums[mid - 1] ? mid : -1;
        		
        		if (nums[mid] <= nums[mid - 1] && nums[mid] <= nums[mid + 1])
        			return mid;
        		else
        			return max(findMin(nums, l, mid - 1), findMin(nums, mid + 1, r));
        	}
        	
        	return -1;
        }
        
        int binarySearch(vector<int>& nums, int l, int r, int& target){
            int m = (l + r)/2;
            while(l <= r){
                if(nums[m] == target)
                    return m;
                else if(nums[m] > target){
                    r = m - 1;
                    m = (l+r)/2;
                }else{
                    l = m + 1;
                    m = (l+r)/2;
                }
            }
            return -1;
        }
    
    public:
        int search(vector<int>& nums, int target) {
            int index = findMin(nums, 0, nums.size() - 1);
            if(index == -1)
                return binarySearch(nums, 0, nums.size() - 1, target);
            return max(binarySearch(nums, 0, index - 1, target), binarySearch(nums, index, nums.size() - 1, target));
        }
    };
    

Log in to reply
 

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