My accepted Java solution with explanation


  • 0
    M
     public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) return Integer.MAX_VALUE;
        else return binarySearch(nums, 0, nums.length - 1);
     }
     private int binarySearch(int[] nums, int start, int end) {
    	if (start >= end) {
    		return nums[end];
    	}
    	int pivot = (start + end)/ 2;
    	// 2. If we got duplicate elements, the fact that for every elements in the array before the minimum will be strictly larger than the elements after the minimum breaks. So we cannot sure which way to go, need to try both! 
    	if (nums[pivot] == nums[end]) return Math.min(binarySearch(nums, start, pivot),  binarySearch(nums, pivot + 1, end));
    	// 1. If we only got distinct elements
    	// If pivot < x <= end, where x is the index for minimum 
    	// Fact: For every elements in the array before the minimum will be strictly larger than the elements after the minimum
    	// Therefore, Given pivot <= end and nums[pivot] < nums[end], it means minimum will not exist between (pivot + 1 , end).
    	if (nums[pivot] < nums[end]) return binarySearch(nums, start, pivot);
    	else return binarySearch(nums, pivot + 1, end);
    }

Log in to reply
 

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