/
Solution.java
32 lines (29 loc) · 1 KB
/
Solution.java
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
package g0101_0200.s0153_find_minimum_in_rotated_sorted_array;
// #Medium #Top_100_Liked_Questions #Array #Binary_Search #Algorithm_II_Day_2_Binary_Search
// #Binary_Search_I_Day_12 #Udemy_Binary_Search #Big_O_Time_O(log_N)_Space_O(log_N)
// #2022_06_25_Time_0_ms_(100.00%)_Space_43.3_MB_(6.36%)
public class Solution {
private int findMinUtil(int[] nums, int l, int r) {
if (l == r) {
return nums[l];
}
int mid = (l + r) / 2;
if (mid == l && nums[mid] < nums[r]) {
return nums[l];
}
if (mid - 1 >= 0 && nums[mid - 1] > nums[mid]) {
return nums[mid];
}
if (nums[mid] < nums[l]) {
return findMinUtil(nums, l, mid - 1);
} else if (nums[mid] > nums[r]) {
return findMinUtil(nums, mid + 1, r);
}
return findMinUtil(nums, l, mid - 1);
}
public int findMin(int[] nums) {
int l = 0;
int r = nums.length - 1;
return findMinUtil(nums, l, r);
}
}