NOIP 普及组初赛 · NOIP 2016 普及组初赛试题 第 14 题

给定含有 $n$ 个不同的数的数组 $L=\text{<}x_{1}, x_{2}, ..., x_{n}\text{>}$。如果 $L$ 中存在 $x_{i}$ $(1<i<n)$ 使得 $x_{1}<x _{2}< \dots < x_{i-1}< x_{i} > x_{i+1}>\dots > x_{n}$ ， 则称 $L$ 是单峰的，并称 $x_{i}$ 是 $L$ 的“峰顶”。现在已知 $L$ 是单峰的,请把 a-c 三行代码补全到算法中使得算法 正确找到 $L$ 的峰顶。

a. Search(k+1, n) b. Search(1, k-1) c. return L[k]

Search(1, n)
1. k←⌊n/2⌋
2. if L[k] > L[k-1] and L[k] > L[k+1]
3. then __________
4. else if L[k] > L[k-1] and L[k] < L[k+1]
5. then __________
6. else __________

正确的填空顺序是（）。

拿到题先别急着看选项，脑子里过一遍单峰数组的样子：先涨后跌。二分找中间点k，比较L[k]和它左右邻居。若L[k]比两边都大，那就是峰顶直接返回；若L[k]比左边大比右边小，说明还在爬坡，峰顶肯定在右边，递归搜右半；否则就是下坡了，峰顶在左边，递归搜左半。顺序就是c、a、b。

最容易掉进两个坑：一是把‘上升段’和‘下降段’反了，以为L[k]比左边大就是下坡，其实那是还在往峰顶爬，得往右找；二是只看了L[k]>L[k-1]这一半条件就急着填a或b，忘了还要看L[k]和L[k+1]的关系，导致逻辑分支混乱。还有种情况是看到题目里有k+1和k-1，下意识想‘是不是要先处理边界’，其实二分法里边界问题已经被题目保证单峰且1<i<n的约束消化了，不用额外特判。

这道题考的是二分查找思想在单峰数组上的应用，核心是‘峰顶’的定义：数组先严格递增到某个位置i，然后严格递减，这个i就是峰顶。题目已经告诉你L是单峰，所以只需要用二分法把峰顶找出来。这里的关键不是写完整代码，而是看懂题目给出的伪代码框架，把三个空填对。伪代码从Search(1,n)开始，第一步取中间点k = floor(n/2)，然后分三种情况处理。

第一种情况是第2行：if L[k] > L[k-1] and L[k] > L[k+1]。这个条件非常直观——中间点比它左右邻居都大，那它只能是峰顶。因为单峰数组里，峰顶是唯一的局部最大值，而且题目保证峰顶不会出现在边界（1<i<n），所以只要L[k]同时大于L[k-1]和L[k+1]，L[k]就是我们要的答案。这时候应该填c，即return L[k]。

第二种情况是第4行：else if L[k] > L[k-1] and L[k] < L[k+1]。这里L[k]比左边大，但比右边小，说明我们正处于上升段，峰顶还没到，而且肯定在k的右边。因为单峰数组是先涨后跌，一旦L[k] < L[k+1]，后面的元素还会继续涨一段才会开始跌，所以峰顶一定在[k+1, n]这个区间里。这时候要填a，即Search(k+1, n)，把搜索范围缩小到右半部分。

第三种情况是第6行：else。如果前两个条件都不满足，那只能是L[k] < L[k-1]或者L[k] > L[k+1]（或者两者都成立，但后者已经被第一个条件覆盖了）。换句话说，L[k]要么比左边小，要么比右边大，这意味着我们已经过了峰顶，正在下降段，峰顶一定在k的左边。这时候要填b，即Search(1, k-1)，把搜索范围缩小到左半部分。

把这三个空按顺序填进去，就是c、a、b，对应选项A。其他选项错在哪里呢？B选项是c、b、a，把上升段和下降段搞反了，如果L[k]在上升段却去搜左边，那就永远找不到峰顶。C和D更是把返回峰顶的操作放到了最后，那前面的递归调用就毫无意义了。

从命题人的角度看，这道题其实是在考你对‘单峰’这个性质的理解，以及二分查找中‘根据中间点与两端的关系决定搜索方向’这一经典套路。很多学生会死记硬背‘大于两边就是峰顶，大于左边小于右边往右，否则往左’，但一旦题目稍微变一下，比如改成找单谷或者给的是非严格单峰，就容易晕。所以做题时还是要回到定义：单峰就是先增后减，峰顶是唯一的局部最大值。然后看中间点k的位置：如果L[k]是局部最大值，那就是峰顶；如果L[k] < L[k+1]，说明还在涨，峰顶在右边；如果L[k] > L[k+1]，说明已经过了峰顶，峰顶在左边。这个逻辑链条非常清晰，只要抓住‘涨’和‘跌’这两个方向，就不会出错。

再看考频和趋势。分支结构在近十年的NOIP普及组初赛里考得相当频繁，题库里一共181题，覆盖从2008到2026的所有级别。逐年分布上，2016年考了12题，2017年12题，2018年10题，最近两年2024年8题、2025年3题、2026年100题（这里2026年100题显然是数据录入错误，实际不可能这么多，但趋势是分支结构依然高频）。分赛事来看，NOIP普及组初赛48题，GESP二级45题，GESP一级25题，其他级别加起来也不少。这说明分支结构是初赛必考内容，而且出题人特别喜欢在算法题里嵌入二分、递归这类需要逻辑判断的结构。

基于这些数据，我预测未来几年，类似这种‘给定某种特殊结构（如单峰、单谷、凸函数等），用二分或递归求极值’的题目还会继续出现，可能是NOIP普及组，也可能是GESP二级或一级。命题人可能会换个包装，比如把数组改成链表，或者把单峰改成‘先增后平再减’，但核心思想不变：抓住中间点与两端的关系，决定搜索方向。所以复习时不要只盯着这道题的填空，要把二分查找、递归、以及各类特殊序列的性质都过一遍，尤其是‘涨’和‘跌’这两个方向在代码里对应的条件怎么写，一定要练熟。

最后再强调一遍易错点：别把‘L[k] > L[k-1]’当成‘已经过了峰顶’，那只是‘还在爬坡’；也别在第一个条件成立时还想着去递归，直接return就行。把这些细节抠清楚，这类题基本就不会丢分了。