LeetCode/153.java at main · vys1n/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// Find Minimum in Rotated Sorted Array
class Solution{
    public int findMin(int[] nums) {
        int l=0, r = nums.length-1;
        int res = nums[0];
        while(l<=r){
            if (nums[l] < nums[r]) {
                res = Math.min(res, nums[l]);
                break;
            }

            int m = l + (r-1) / 2;
            res = Math.min(res, nums[m]);
            if (nums[m] >= nums[l]) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return res;
    }

    // Binary Search (Lower Bound)
    public int findMinLB(int[] nums){
        int l=0, r = nums.length-1;
        while(l<r){
            int m = l + (r-l) / 2;
            if (nums[m] < nums[r])
                r = m;
            else
                l = m+1;
        }
        return nums[l];
    }
}