LeetCode - Find Minimum in Rotated Sorted Array
Problem description
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
Example 1:
1
2
Input: [3,4,5,1,2]
Output: 1
Example 2:
1
2
Input: [4,5,6,7,0,1,2]
Output: 0
Analysis
Just use the binary search we can find the answer. There’s an observation that the left is always bigger than the right if it’s rotated. So we can use this to find out the minimum one.
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
class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0){
return -1;
}
if (nums.length == 1){
return nums[0];
}
return find(nums, 0, nums.length - 1);
}
int find(int[] nums, int l, int h){
if (nums[h] > nums[l]) {
return nums[l];
}
int mid = l + (h-l)/2;
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 (nums[mid] > nums[h]){
return find(nums, mid+1, h);
}
else{
return find(nums, l, mid-1);
}
}
}
What to improve
