-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinRotSortArr.java
More file actions
49 lines (43 loc) · 1.62 KB
/
MinRotSortArr.java
File metadata and controls
49 lines (43 loc) · 1.62 KB
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;
class MinRotSortArr {
public static int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
System.out.println("9l: " + nums[left]);
System.out.println("10r: " + nums[right]);
int mid = (right + left) / 2;
System.out.println("12mid: " + nums[mid]);
// Check if mid is in the rotated part or sorted part
// {4,5,1,2,3}; n[l] = 4; n[r] = 3; n[m] = 1
if (nums[mid] > nums[right]) {
// Min must be in right half; search the right; move left to mid + 1
left = mid + 1;
System.out.println("17L: " + nums[left]);
} else {
// Min could be mid or in the left half; move right to mid => {4,5,1}
right = mid;
System.out.println("21R: " + nums[right]);
}
}
return nums[left];
}
public static void main(String[] args) {
int[] nums = {4,5,1,2,3};
System.out.println(findMin(nums));
}
}
/*
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
1. Binary Search Loop
Narrow range [left, right] until left = right
2. Condition Check
[3, 4, 5, 1, 2]
[4, 5, 1, 2, 3] => [4, 5, 1]
nums[mid] > nums[right]: rotation on right side so move left to mid + 1; search the right side
nums[mid] <= nums[right]: min is on left side or is nums[mid], so move right to mid
3. Return result
When left == right, min elem is at nums[left]
Time: O(log n): performing binary search
Space: O(1): Using constant space
*/