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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class {
public int findMin(int[] array) {
if (array == null || array.length == 0) {
return -1;
}
int lb = 0;
int ub = array.length - 1;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (array[mid] < array[ub]) {
ub = mid;
} else if (array[mid] > array[ub]){
lb = mid;
} else {
lb++;
}
}
return Math.min(array[lb], array[ub]);
}
}
|
近期评论