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

正确的填空顺序是（）。

选项

• A. c,a,b
• B. c,b,a
• C. a,b,c
• D. b,a,c

答案

A

题解

考点定位

本题考「单峰序列折半查找」,对应大纲 4.3.1 二分（难度【4】）。

解题过程

单峰序列：先升后降，峰值最大。折半比较 mid 与 mid+1：mid<mid+1 在上升段 → 峰在右。三元素 x₁<x₂>x₃ 型（单峰）：二分定位峰值位置对应的下标组合。按官方答案（c,a,b）：候选下标 a,b,c 的输出顺序为 c,a,b。

选 A。

易错提醒

① 单峰折半判据：mid 与 mid+1 比较（不是与 target）；② 第一次 mid 落在峰右侧/左侧决定后续区间，手动代入 n=3 最直观。