Twenty Percent Knowledge: minimum in rotated array

Thursday, July 07, 2016

Find Minimum in Rotated Sorted Array

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.

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
         
        int l = 0;
        int r = nums.length - 1;
         
        while (l+1 < r) {//deal with one or two numbers
            int mid = l + (r - l) / 2;
             
            if (nums[l] < nums[r]) {//sorted, no rotation
                return nums[l];
            } else if (nums[mid] < nums[r]) {//right is sorted,pivot point is in left,
            //get rid of right array by redefining r
                r = mid;
            } else if (nums[l] < nums[mid]) {//left is sorted, pivot is in right, 
            //redefine left point by move left to mid
                l = mid;
            }
        }
         
        return Math.min(nums[l], nums[r]);
    }
}