网站建设 探索公司主页怎么写

剑指 Offer 11. 旋转数组的最小数字

二分
要注意的是，由于存在重复数字，所以初始状态可能不满足二分的性质。不满足的情况是：左边开始的数字和右边结束的数字相等，所以一开始要缩小右边界，让右边界的数字小于第一个数字。这样左边的数字都大于等于第一个数字，右边的数字都小于第一个数字，两个区间的性质不同，就可以进行二分了。还有排除递增的情况。

class Solution {public int minArray(int[] numbers) {int l = 0, r = numbers.length - 1;while(r > 0 && numbers[r] == numbers[0]) r--;  // 缩小右边界if(numbers[r] >= numbers[0]) return numbers[0];  // 排除递增的情况while(l < r){int mid = (l + r) >> 1;if(numbers[mid] >= numbers[0]) l = mid + 1;else r = mid;}return numbers[l];}
}