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.

Example:

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

Solution:

Assume we have a sorted array [c, ..., b] and we rotate it at pivot a, then we have a rotated array [a, ..., b, c, ...., d], where c is the smallest value and b is the largest. As illustrated by following figure.

We could choose d as the target for binary search.

• If mid element is less than or equal to d, we move the end to mid.
• If mid element is greater than d, we move the start to mid.
• When there are only two elements left, one of them will be c.

Code:

public int findMin(int[] nums) {
    if (nums == null || nums.length == 0) {
        return Integer.MAX_VALUE;
    }
    int start = 0;
    int end = nums.length - 1;
    int target = nums[end];
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] <= target) {
            end = mid;
        } else {
            start = mid;
        }
    }
    if (nums[start] < nums[end]) {
        return nums[start];
    } else {
        return nums[end];
    }
}