153.Find Minimum in Rotated Sorted Array

Posted on | In

Solution 1: accepted 0ms

use nums[mid] > nums[hi] rather than nums[mid] > nums[lo] to avoid consideration of corner case, no rotation. If there’s no rotation and we say if (nums[mid] > nums[lo]) lo = mid, we abandon the left side, which has the answer. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findMin(int[] nums) {
    if (nums.length == 0) return -1;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi])
            lo = mid;
        else
            hi = mid;
    }
    return nums[lo] < nums[hi] ? nums[lo] : nums[hi];
}