二分查找

62 寻找峰值
题意解读
看一下灵神的思路：

首先读懂题目，为什么要规定 nums[−1]=nums[n]=−∞？也就是假设 nums[0] 的左边还有一个 −∞，nums[n−1] 的右边还有一个 −∞。

因为这可以保证数组一定有峰值。比如数组是严格递减的，那么 nums[0] 就是（唯一的）峰值。为什么？因为此时 nums[−1]<nums[0]>nums[1]。注意 −∞ 可以保证 nums[0] 一定比它左边的数大。同理，如果数组是严格递增的，那么 nums[n−1] 就是（唯一的）峰值。

性质分析
定理：如果 i<n−1 且 nums[i]<nums[i+1]，那么在下标 [i+1,n−1] 中一定存在峰值。

证明：反证法，假设下标 [i+1,n−1] 中没有峰值。

由于 i+1 不是峰值且 nums[i]<nums[i+1]，所以一定有 nums[i+1]<nums[i+2] 成立，否则 i+1 就是峰值了。注意题目保证相邻元素不同，不存在相邻元素相等的情况。
由于 i+2 不是峰值且 nums[i+1]<nums[i+2]，所以一定有 nums[i+2]<nums[i+3] 成立，否则 i+2 就是峰值了。

依此类推，得
nums[i]<nums[i+1]<nums[i+2]<⋯<nums[n−1]>nums[n]=−∞
这意味着 nums[n−1] 是峰值，矛盾，所以原命题成立。
同理可得，如果 i<n−1 且 nums[i]>nums[i+1]，那么在 [0,i] 中一定存在峰值。

所以，通过比较 nums[i] 和 nums[i+1] 的大小关系，可以二分找到峰值。

二分定义
下面代码采用开区间二分，这仅仅是二分的一种写法，使用闭区间或者半闭半开区间都是可以的，喜欢哪种写法就用哪种。

循环不变量：

left 的下标中存在峰值下标。
≤right 的下标中存在峰值下标。
换句话说，任意时刻均满足 (left,right] 中存在峰值下标。
在二分过程中，我们能确定的是区间 (left,right] 里面一定有峰值。区间外面有没有峰值？可能有，也可能没有。

常见误区：很多同学会把二分范围与答案范围混为一谈。请注意，二分范围 (left,right) 与答案范围 (left,right] 是不一样的。比如二分循环结束的时候，二分范围是空的，你总不能说答案在空区间里面吧！

不是因为开区间只能找到一个峰值

而是因为二分不断缩小范围

最后答案区间只剩一个位置

这个位置恰好是某个峰值

所以返回 right（或者对应模板里的 left+1）

只能保证找到一个峰值，所以最后要返回left+1=right的时候，就是返回right

开区间二分循环结束后 left+1=right，由于 (left,right] 中只有 right 一个数，所以答案是 right。

常见误区：如果有多个峰值，我们无法在一开始、以及二分过程中就确定哪个峰值最终会成为答案。二分的思路只是不断地缩小范围，并最终找到其中的一个峰值。尤其在二分过程中，nums[i]<nums[i+1] 并不意味着 i 右边的第一个峰值一定会是最终答案。

细节
二分范围（注意是二分范围不是答案范围）是开区间 (−1,n−1)，也就是闭区间 [0,n−2]。

为什么二分范围不用包含 n−1？

这是因为，如果有且仅有一个峰值，且其下标是 n−1，那么一定有

nums[0]<nums[1]<nums[2]<⋯<nums[n−1]
这意味着每次二分更新的都是 left，最终答案自然就是 n−1。

注意本题答案是存在的，即 [0,n−1] 中一定存在峰值，这可以用上文中的反证法证明。

class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left, right = -1, len(nums) - 1 # 开区间 (-1, n-1)
while left + 1 < right: # 开区间不为空
mid = (left + right) // 2
if nums[mid] > nums[mid + 1]: # 下坡，峰顶位置 <= mid
right = mid
else: # 上坡，峰顶位置 > mid
left = mid
return right
复杂度分析
时间复杂度：O(logn)，其中 n 是 nums 的长度。
空间复杂度：O(1)。

1. 前提条件

题目给一个数组：

int* nums;
int numsSize;

峰值定义：
nums[i] > nums[i-1]
并且
nums[i] > nums[i+1]

题目还认为：

nums[-1] = -∞
nums[n] = -∞

所以边界也可能是峰值。

2. 核心概念

看相邻两个数：

nums[mid] 和 nums[mid+1]

如果：

nums[mid] < nums[mid+1]

说明现在是上坡：

mid -> mid+1

那右边一定存在峰值。

如果：

nums[mid] > nums[mid+1]

说明现在是下坡：

mid -> mid+1

那左边，包括 mid，一定存在峰值。

3. 为什么上坡右边一定有峰值？

比如：

1 2 3 4

一直上坡，最后一个就是峰值，因为右边是 -∞。

如果中途开始下降：

1 2 5 3

转折点 5 就是峰值。

所以：
只要 nums[mid] < nums[mid+1]
右边一定有峰值。

4. 为什么下坡左边一定有峰值？

比如：
4 3 2 1

一直下坡，第一个就是峰值，因为左边是 -∞。

如果左边曾经上升又下降：

1 5 3 2

转折点 5 就是峰值。

所以：
只要 nums[mid] > nums[mid+1]
左边一定有峰值。

5. 二分模板

这里用闭区间：[left, right]

每次比较：

nums[mid] 和 nums[mid+1]

所以 mid+1 不能越界。

因此循环条件写：

while (left < right)

6. C 代码
   int findPeakElement(int* nums, int numsSize) {
   int left = 0;
   int right = numsSize - 1;

   while (left < right) {
   int mid = left + (right - left) / 2;

    if (nums[mid] < nums[mid + 1]) {
        left = mid + 1;
    } else {
        right = mid;
    }
   

   }

   return left;
   }
   这里是保证最后的取等条件是left=right，所以返回哪个都无所谓

7. 例题流程
   nums = [1,2,1,3,5,6,4]

初始：

left = 0
right = 6
第一轮
mid = 3
nums[3] = 3
nums[4] = 5

因为：

3 < 5

说明右边有峰值。

所以：

left = mid + 1 = 4

范围变成：

[4,6]
第二轮
mid = 5
nums[5] = 6
nums[6] = 4

因为：

6 > 4

说明左边有峰值，包括 mid。

所以：

right = mid = 5

范围变成：

[4,5]
第三轮
mid = 4
nums[4] = 5
nums[5] = 6

因为：

5 < 6

右边有峰值。

所以：

left = 5

结束：

left = right = 5

返回：

5

对应：

nums[5] = 6

8. 易错点
   易错点 1：不是找最大值

峰值不一定是全局最大。

例如：

[1,2,1,3,5,6,4]

峰值可以是：

2 或 6

返回任意一个峰值都行。

易错点 2：比较的是 mid 和 mid+1

不是直接判断：

nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]

二分的核心是判断哪边一定有峰值。

易错点 3：right = mid，不是 mid - 1

当：

nums[mid] > nums[mid+1]

mid 自己就可能是峰值。

所以不能丢掉 mid。

正确：right = mid;

9. 总结
   核心：
   比较 nums[mid] 和 nums[mid+1]

如果 nums[mid] < nums[mid+1]：

说明右边是上坡方向

右边一定有峰值

left = mid + 1

如果 nums[mid] > nums[mid+1]：

说明左边是下坡方向

左边一定有峰值

right = mid

---

循环：

while(left < right)

---

答案：left 或 right

---

每次保留一个一定存在峰值的区间。

寻找峰值的二分不是找某个确定值，而是根据坡度方向，保留一定有峰值的一半。