154.Find Minimum in Rotated Sorted Array II

Posted on | In

Teat cases

1
2
3
4
5
6
[1]
[7,8,9,1,2,3,4,5,6]
[7,8,9,9,9,9,1,2,3,3,4,5,5,5,6,6,6,6]
[1,1,1,1,1,1,1,1]
[2,3,4,5,6,7,8,1]
[3,4,5,6,7,8,1,2]

Solution 1: accepted 1ms

Time: O(n) // worst case when all elements are the same 

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 if (nums[mid] < nums[hi])
            hi = mid;
        else
            hi--;
    }
    return nums[lo] <= nums[hi] ? nums[lo] : nums[hi];
}