MIT算法导论L1：分治寻峰算法逻辑疑问咨询

先明确MIT算法导论里的这个寻峰分治算法核心逻辑：针对长度为n的数组，检查中间位置n/2：

1. 若a[n/2] < a[n/2-1]，则在左半区间1...n/2-1继续寻找；
2. 否则若a[n/2] < a[n/2+1]，则在右半区间n/2+1...n继续寻找；
3. 否则n/2就是峰。

针对你的三个疑惑，逐一解释：

1. 为何a[n/2] < a[n/2-1]时左半部分必存在峰？ #

当中间元素比左邻居小的时候，我们可以沿着左半部分的方向推导：

• 从n/2-1开始往左看，要么这个元素一直比它的左邻居大，直到数组左端点——此时左端点就是峰（因为它没有左邻居，只要比右边的元素大就满足峰的定义）；
• 要么在左半部分的某个位置i，出现a[i] >= a[i-1]，同时因为a[i] >= a[i+1]（否则我们会继续往左走），这个i就是峰。
  不管哪种情况，左半部分一定存在至少一个峰，所以完全可以舍弃右半部分，专注左半部分即可。反之，当a[n/2] < a[n/2+1]时，右半部分的推导逻辑是一样的，必然存在峰。

2. 关于条件真假与峰位置的误解纠正 #

你之前搞反逻辑是因为没理清条件对应的趋势：
当a[n/2] < a[n/2-1]为真时，左半部分是“向上走”的趋势（从中间往左，元素越来越大），所以必然能找到峰；
当这个条件为假时，说明a[n/2] >= a[n/2-1]，此时有两种可能：

• 如果a[n/2] < a[n/2+1]，说明右半部分是向上走的趋势，去右半部分找峰；
• 如果a[n/2] >= a[n/2+1]，那中间位置本身就是峰。
  所以这个条件为假时，左半部分不一定存在峰，但中间或右半部分一定有，这就是为什么算法不会往左边走的原因。

3. 为何视频中会提及条件为假时的处理逻辑？ #

算法的if...else分支是为了覆盖所有可能的情况：
第一个条件处理“中间比左邻居小”的情况；
else分支处理“中间不比左邻居小”的所有情况，这时候需要进一步判断中间和右邻居的关系——要么去右半部分，要么直接返回中间。
每一个分支都是必要的，确保无论数组是什么情况，算法都能找到一个峰，不会出现遗漏。

内容的提问来源于stack exchange，提问作者thegamerguy