Question

Formatted question description: https://leetcode.ca/all/153.html

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

@tag-array

Algorithm

Compare the middle value nums[mid] with the right boundary value nums[right]. If the array is not rotated or the rotation point is in the left half, the middle value must be less than the right boundary value, so go to the left half to continue searching , Otherwise, go to the right half to search, and finally return nums[right].

Code

Java

public class Find_Minimum_in_Rotated_Sorted_Array {

	public class Solution_iteration {
	    public int findMin(int[] nums) {

	        if (nums == null || nums.length == 0) {
	            return 0;
	        }

	        // min is possibly found in 3 cases (eg. 1,2,3,4,5):
	        // 1. min at left half (eg. 5,1,2,3,4)
	        // 2. min at right half (eg. 2,3,4,5,1)
	        // 3. min at mid position (eg. 4,5,1,2,3)


            // 2 cases:
            // 1,2,3,4,5 // @note:@memorize: but this case is included in above if check
            // 2,3,4,5,1

	        int low = 0; // left pointer
	        int high = nums.length - 1; // right pointer

	        /* @note: to restore thinking process
	        while (low <= high) {
	            int mid = low + (high - low) / 2;

	            if (nums[low] < nums[high]) { // meaning not rotated
	                return nums[low];

	            } else if (nums[mid] > nums[low]) { // left part sorted
	                low = mid;

	            } else { // (nums[mid] <= nums[i]) { // right part sorted @note: '=' is crucial
	                // j = mid - 1;
	                high = mid;
	            }
	        }
	        */

	        while (low < high && nums[low] > nums[high]) { // @note: if low < high, then un-rotated, return low

	        	int mid = low + (high - low) / 2;

	        	if (nums[mid] > nums[high]) {
	        		low = mid + 1;
	        	} else {
	        		high = mid; // @note: here, not "high=mid-1"
	        	}

	        	/*
	        	 * @note: below not working, for input [2,1], infinite loop
							why?
							because, if mid>high, then mid is never min, so mid+1
									 if mid<=high, then mid could be max

							in this case, if change the question to be, "find max in rotated sorted array"?
							then, the mid check is the opposite

		        	if (nums[mid] > nums[high]) {
		        		low = mid;
		        	} else {
		        		high = mid - 1;
		        	}

	        	 */
	        }

	        return nums[low];
	    }
	}
}

All Problems

All Solutions