题目
方法一-二分法
设数组最后一个元素为 x ，在最小元素右侧的元素，它们的值一定都小于等于 x ；在最小元素左侧的元素，它们的值一定都大于等于 x 。
在二分查找每一步中，设左边界为
l
o
w
low
low，右边界为
h
i
g
h
high
high，区间中点为
p
i
v
o
t
pivot
pivot。将中轴元素
n
u
m
b
e
r
s
[
p
i
v
o
t
]
numbers[pivot]
numbers[pivot] 与右边界元素
n
u
m
b
e
r
s
[
h
i
g
h
]
numbers[high]
numbers[high] 进行比较：
- 当 n u m b e r s [ p i v o t ] < n u m b e r s [ h i g h ] numbers[pivot] < numbers[high] numbers[pivot]<numbers[high]时，说明中轴元素在最小元素右侧，可以忽略查找区间的右半部分。
- 当 n u m b e r s [ p i v o t ] > n u m b e r s [ h i g h ] numbers[pivot] > numbers[high] numbers[pivot]>numbers[high]时，说明中轴元素在最小元素左侧，可以忽略查找区间的左半部分。
- 当 n u m b e r s [ p i v o t ] = n u m b e r s [ h i g h ] numbers[pivot] = numbers[high] numbers[pivot]=numbers[high]时，无法判断中轴元素和最小元素的位置关系，但可以确保无论右边界元素是不是最小元素，都存在替代品，即中轴元素，所以可以忽略右边界元素，即，将区间右端向左缩小一位继续查找。
class Solution {
public int minArray(int[] numbers) {
int low = 0;
int high = numbers.length - 1;
while(low < high){
int pivot = low + (high - low)/2;
if(numbers[pivot] < numbers[high]){
high = pivot;//中轴元素小于右边界元素，中轴元素也可能是最小元素
}else if(numbers[pivot] > numbers[high]){
low = pivot + 1;//中轴元素大于右边界元素，所以中轴元素一定不是最小元素
}else{
high -= 1;
}
}
return numbers[low];
}
}
notes：关于二分时用的是 l o w + ( h i g h − l o w ) / 2 low + (high - low)/2 low+(high−low)/2而非 ( l o w + h i g h ) / 2 (low + high)/2 (low+high)/2，是为了避免两数相加时发生溢出。
- 时间复杂度：平均时间复杂度为 O ( l o g n ) O(log n) O(logn)，其中n为数组长度；最坏情况下，数组中元素完全相同，while循环就要执行 n 次，时间复杂度为 O ( n ) O(n) O(n)
- 空间复杂度： O ( 1 ) O(1) O(1)