Suppose a sorted array 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.
数列基本有序，使用二分查找。分为3种情况：
假设数列是n，s是起始下标，e是最后下标，m是中间元素下标。
ns < ne
0 1 2 4 5 6 7
这种情况，直接返回ns。因为数列是有序的，或者只是旋转过一次。如果ns < ne，则表明没有旋转。最小元素是ns。
nm > ns > ne
4 5 6 7 0 1 2
只需要满足nm > ns即可，因为第一种情况排除后，ns就一定会 > ne。
在本例中：
ns = 4
nm = 7
ne = 2
则最小值肯定在7之后，到2之间，即 m 1, e。
nm < ne < ns
6 7 0 1 2 4 5
nm < ne，在本例中：
ns = 6
nm = 1
ne = 5
则表明，从m到e，数组已经是上升的，所以最小值在s, m。
代码语言：javascript复制 public int findMin(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
if (nums.length == 2) {
return Math.min(nums[0], nums[1]);
}
int s = 0, e = nums.length - 1;
int m = (s e) / 2;
if (nums[s] < nums[e]) {
return nums[s];
}
if (nums[m] > nums[s]) {
return findMin(Arrays.copyOfRange(nums, m 1, e 1));
}
return findMin(Arrays.copyOfRange(nums, s, m 1));
}
