NOIP 提高组初赛 · NOIP 2016 提高组初赛试题 第 15 题

给定含有 $n$ 个不同的数的数组 $L=\text{<}x_1,x_2,\dots,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 __________  

正确的填空顺序是（ ）。

这道题考的是单峰序列的二分查找。拿到题先想：二分判定的核心就是看当前中点 L[k] 和它右边邻居 L[k+1] 的大小关系。如果 L[k] < L[k+1]，说明序列还在上升，峰顶肯定在右半区；反之，如果 L[k] > L[k+1]，说明已经过了峰顶，峰顶在左半区。所以填空顺序就是：先判断是否找到峰顶（c），再根据方向决定递归哪半边（a 或 b）。

最容易错的两个坑：一是把逻辑搞反，以为 L[k] < L[k+1] 就该去左边，其实那是上升段，峰顶只能在右边；二是看到 else 就下意识填 Search(1, k-1)，其实 else 对应的是 L[k] > L[k+1] 的情况，这时候峰顶在左边，必须填 Search(1, k-1)，而 L[k] < L[k+1] 的情况必须填 Search(k+1, n)。很多同学会在这两个 else-if 分支里把 a 和 b 的顺序填反，导致整个算法逻辑全乱。

考点概念：单峰序列的二分查找

单峰序列就是先严格递增、后严格递减的序列。题目给出的算法框架是一个典型的二分查找：每次取中间点 k，比较 L[k] 和它右边邻居 L[k+1] 的大小，从而判断峰顶在左半区还是右半区。

命题视角：为什么考这个？

命题人想考的是你对“单调性”和“二分判定”的直觉。在单峰序列里，只要看到 L[k] < L[k+1]，就立刻能断定：从 k 到 k+1 还在上升，峰顶不可能在 k 或 k 左边，一定在 k+1 右边；反之，如果 L[k] > L[k+1]，说明从 k 到 k+1 已经开始下降了，峰顶一定在 k 或 k 左边。这种“看一步定方向”的思维方式，是二分查找在有序（或单峰）序列上的核心。