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.

Notice

You may assume no duplicate exists in the array.

Example Given [4, 5, 6, 7, 0, 1, 2] return 0

Solution: The key point to do this kind of question is that half array must be sorted. So we can use Binary Search. Because this question has no target, we need to keep track the minimum with end pointer(if mid is exactly the minimum, we can not minus 1)

public int findMin(int[] nums) {
    if(nums == null || nums.length == 0) {
        return 0;
    }
    int start = 0, end = nums.length - 1;

    while(start < end) {
        int mid = start + (end - start) / 2;
        if(nums[start] < nums[end]) {
            return nums[start];
        }
        if(nums[start] <= nums[mid]) {
            start = mid + 1;
        }
        else {
            end = mid;
        }
    }
    return nums[start];
}

Find Minimum in Rotated Sorted Array II

The array may contain duplicates.

Example Given [4,4,5,6,7,0,1,2] return 0.

Solution: If duplicate skip that element.

public int findMin(int[] nums) {
    if(nums == null || nums.length == 0) {
        return 0;
    }
    int start = 0, end = nums.length - 1;

    while(start < end) {
        int mid = start + (end - start) / 2;
        if(nums[start] < nums[end]) {
            return nums[start];
        }
        if(nums[start] < nums[mid]) {
            start = mid + 1;
        }
        else if(nums[start] > nums[mid]) {
            end = mid;
        }
        else {
            start++;
        }
    }
    return nums[start];
}