153. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order 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.

Solution:

In a rotated sorted array, the minimum element is alway smaller or equal to the end element in the array.

Therefore, we use this element as target, and use binary search to find the first element in the array that is smaller or equal to it.

The time complexity for binary search is O(logn).



Code:

public class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        int target = nums[nums.length - 1];
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] > target) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        return Math.min(nums[start], nums[end]);
    }
}