C++ 4ms recursive solution using binary search


  • 2
    J

    the bsearch function is to find the index of minimum number;

    if nums[mid] is smaller than both nums[mid - 1] and nums[mid + 1], then the index is mid

    otherwise, recursively call bsearch(nums, l, mid -1) and bsearch(nums, mid +1 ,r)

    if cannot find in one half, return -1, then the result is the larger one of two half

    class Solution {
        int bsearch(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(bsearch(nums, l, mid - 1), bsearch(nums, mid + 1, r));
        	}
        	
        	return -1;
        }
    public:
        int findMin(vector<int>& nums) {
            int t = bsearch(nums, 0, nums.size() - 1);
            return t == -1?nums[0] : nums[t];
        }
    };

  • 3
    W

    My nonrecursive version:

    class Solution {
    public:
        int findMin(vector<int>& nums) {
            if (nums[0] <= nums[nums.size() - 1]) {
                return nums[0];
            }
            int i = 0, j = nums.size() - 1;
            while (i + 1 < j) {
                int k = (i + j) / 2;
                if (nums[i] > nums[k]) {
                    j = k;
                }
                else {
                    i = k;
                }
            }
            return nums[j];
        }
    };

Log in to reply
 

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