-
Notifications
You must be signed in to change notification settings - Fork 0
/
find-minimum-in-rotated-sorted-array.java
47 lines (41 loc) · 1.5 KB
/
find-minimum-in-rotated-sorted-array.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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public int findMin(int[] nums) {
// If the list has just one element then return that element.
if (nums.length == 1) {
return nums[0];
}
// initializing left and right pointers.
int left = 0, right = nums.length - 1;
// if the last element is greater than the first element then there is no rotation.
// e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
// Hence the smallest element is first element. A[0]
if (nums[right] > nums[0]) {
return nums[0];
}
// Binary search way
while (right >= left) {
// Find the mid element
int mid = (left + right ) / 2;
// if the mid element is greater than its next element then mid+1 element is the smallest
// This point would be the point of change. From higher to lower value.
if (nums[mid] > nums[mid + 1]) {
return nums[mid + 1];
}
// if the mid element is lesser than its previous element then mid element is the smallest
if (nums[mid - 1] > nums[mid]) {
return nums[mid];
}
// if the mid elements value is greater than the 0th element this means
// the least value is still somewhere to the right as we are still dealing with elements
// greater than nums[0]
if (nums[mid] > nums[0]) {
left = mid + 1;
} else {
// if nums[0] is greater than the mid value then this means the smallest value is somewhere to
// the left
right = mid - 1;
}
}
return -1;
}
}