思路:
可以直接遍历,二分的复杂度更好一点
注意!!!可能重复!!!
class Solution {
public int minArray(int[] numbers) {
int l=0,r=numbers.length-1;
while(l<r){
int mid=(l+r)/2;
if(numbers[r]>numbers[mid]) r=mid;
else if(numbers[r]<numbers[mid]) l=mid+1;
else r--;
}
return numbers[l];
}
}
当numbers[mid]==numbers[r]
。如下图所示,由于重复元素的存在,我们并不能确定numbers[mid]
究竟在最小值的左侧还是右侧,因此我们不能莽撞地忽略某一部分的元素。我们唯一可以知道的是,由于它们的值相同,所以无论 numbers[r]
是不是最小值,都有一个它的「替代品」numbers[mid]
,因此我们可以忽略二分查找区间的右端点,直接r-1
。