一、寻找旋转排序数组中的最小值
-
旋转后的数组：分为两段，都是升序的
- 第一段的第一个元素比第二段任何一个都要大
-
寻找最小值
- 实际上：寻找第二段的第一个元素，也即是原数组的翻转点
-
利用二分法，将第二段第一个元素作为目标target
- 当中间元素值小于target，则区间应该改为中间元素的左边
- 因为第二段的第一个元素可能在左边，右边值更大舍弃，right = center - 1
- 当大于等于时，区间改为中间元素的右边
- 因为当前的中间元素是属于第一段的，应该到右边找第二段的第一个元素，left = center + 1
- 不难看出，最后left指针会指向第二段的第一个元素
- 但如果第二段不存在，即翻转次数为数字长度的整数倍时，最小值应为第一段的最小值，left下标对数组长度取余即可
- 当中间元素值小于target，则区间应该改为中间元素的左边
class Solution { public int findMin(int[] nums) { //二分法寻找第二段的最小值，也即是翻转点 int left = 0; int right = nums.length - 1; int target = nums[0];//第一段升序数组的最小值 while(left <= right) { int center = left + (right - left) / 2; if(nums[center] >= target) {//中间元素的值比第一段的第一个值大 left = center + 1;//翻转点在中间指针的左边 } else { right = center - 1; } } return nums[left % nums.length]; } }
二、寻找峰值
-
数组中的任何给定序列视为交替的升序和降序序列
- 符合二分有序的要求
-
从数组 nums 中的区间找到中间的元素 mid
- 若该元素恰好位于降序序列或者一个局部下降坡度中（ nums[i] <= nums[i + 1] )，则说明峰值会在本元素的左边
- 将搜索空间缩小为 midmid 的左边(包括其本身)
- 若该元素恰好位于升序序列或者一个局部上升坡度中（ nums[i] > nums[i + 1] )，则说明峰值会在本元素的右边
- 将搜索空间缩小为 midmid 的右边
- 重复上述过程
- 不断地缩小搜索空间，直到搜索空间中只有一个元素，该元素即为峰值元素
- 若该元素恰好位于降序序列或者一个局部下降坡度中（ nums[i] <= nums[i + 1] )，则说明峰值会在本元素的左边
nums[-1] = nums[n] = -∞：只要数组中存在一个元素比相邻元素大，那么沿着它一定可以找到一个峰值
这个可以用反证法，如果这句不成立，比如mid 的元素大于mid +1，那么左边一定有峰值。如果没有，你从mid -1，开始往前推，会发现，要保证这点，就会出现元素0>1>2>...>mid -2>mid-1>mid。即使这样，由于-1是无穷小，那么0这个点也是峰值
class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while(left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
