GESP 五级 · GESP 202312 C++ 五级 第 10 题

在上题的 _binarySearch 算法中，如果 lst 中有 $N$ 个元素，其时间复杂度是（ ）。

这题其实就考一个核心直觉：二分每次把范围砍一半，N 到 1 需要砍多少次？次数就是 log₂N，所以复杂度是 O(log N)。

最容易错在把二分和排序混为一谈，看到‘二分前数组要有序’就下意识选 O(N log N)，但题目问的是二分算法本身的时间复杂度，排序是前置条件不在算法内部。另一个坑是误以为循环次数和元素个数成正比，其实二分循环次数只和 log N 成正比，和 N 本身没关系。

【考点】二分查找｜时间复杂度分析｜对数阶运算

1. 考纲定位 本题考查 GESP 五级《基本算法》模块中二分查找算法的时间复杂度。命题人专门在此处埋题，就是为了卡住那些只背“二分查找快”却说不清“快多少”的考生——五级要求从定性理解升级到定量分析，这是区分三级和五级的关键分水岭。

2. 解题思维 看到“二分查找”四个字，立刻反应出核心机制：每次比较都将搜索区间对半削减。N 个元素，第一次剩 N/2，第二次剩 N/4，第 k 次剩 N/(2^k)。当 N/(2^k) ≈ 1 时找到目标，解得 k ≈ log₂N。因此操作次数与 log₂N 同阶，即 O(log N)。记住这个“减半模型”，以后遇到任何“每次减少固定比例”的算法都能直接套用。

3. 陷阱拆解

• A 项 O(N) 是线性查找的复杂度，混淆二分与遍历的人必选
• C 项 O(N log N) 是排序算法（快排/归并）的复杂度，把二分和排序混为一谈的陷阱
• D 项 O(N²) 是双重循环的典型复杂度，完全偏离二分思路

最阴险的是 C 项——命题人利用考生对“二分需要有序”这点的记忆，暗示“要先把数组排好序（O(N log N)）再二分”，偷换概念！二分查找本身只负责查，排序是前置条件，不在本题问的算法内部。

4. 反命题思维 若把题中“二分查找”换成“线性查找”，答案立刻变 A；若改成“先排序再二分”，答案变 C。刷到这类题，先问自己：“这算法内部每一步到底砍掉多少？”——砍掉一半就是 log N，砍掉常数就是 O(N)，砍掉平方就是 O(N²)。掌握这个对应关系，复杂度题就难不倒你。

5. 考频趋势 二分查考频在题库中为 39 题，覆盖 7 个级别，其中 GESP 五级独占 16 题，占比超过四成，是五级高频考点。复杂度分析在题库中为 39 题，但仅覆盖 2 个级别（2026 年 11 题、null 年 28 题），说明纯复杂度题目前较少，多依附于具体算法。

6. 预测 基于数据，未来 GESP 五级仍可能继续高频考查二分查找及其复杂度，但纯复杂度分析题因缺乏历史支撑，暂无足够依据预测其独立出现趋势。