[LeetCode] Problem 153 - Find Minimum in Rotated Sorted Array

Posted on | In ,

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.

Example

No.1

Input: [3,4,5,1,2]

Output: 1

No.2

Input: [4,5,6,7,0,1,2]

Output: 0

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        int middle = (left + right) >> 1;

        if (nums[middle] > nums[right])
            left = middle + 1;
        else
            right = middle;
    }

    return nums[left];
}