GESP 五级 · GESP 202512 C++ 五级 第 20 题

二分查找仅适用于有序数据。若输入数据无序，当仅进行一次查找时，为了使用二分而排序通常不划算。

比较不同排序算法的核心区别：冒泡（相邻交换）、选择（选最值）、插入（插入有序序列）、归并（分治合并）、快排（划分递归）。

排序稳定性指相等元素排序后相对顺序是否改变。稳定：冒泡、插入、归并。不稳定：选择、快排、堆排。

【考点】二分查找｜排序算法｜时间复杂度

考纲定位：本题考查《GESP 考试大纲》五级“数据结构与算法”模块的复合应用。命题人卡住的是考生对二分查找适用条件的机械记忆——许多学生只背“二分需有序”，却忽略排序本身需 O(n log n) 时间，而单次查找 O(log n) 已足够快，排序反而更慢。

解题思维：看到“仅进行一次查找”先锁定比较次数：直接扫描 O(n)，二分 O(log n)。再想排序代价：无论冒泡、快排、堆排，最典型都是 O(n log n)。因此排序后二分总耗时 O(n log n) 远大于直接扫描 O(n)，排序不划算。通法：任何“为单次查找排序”的题，先算排序时间，再与查找时间对比，若排序时间 > 查找时间则排序必亏。

陷阱拆解：错项 B 通常源于混淆“有序才能二分”与“排序必须做”——命题人利用“二分需有序”的条件，却偷换概念把“需有序”等同于“必须排序”，忽略已有有序数据的情况。另一陷阱是绝对化表述“通常不划算”，若考生只记结论而不理解复杂度权衡，就会误判边界情况（如数组已部分有序、数据量极小等）。

反命题思维：若把题干改为“在已知数据无序但允许多次查找时，是否应排序？”，答案会翻转：当查找次数 > n/log n 时排序反而划算。刷到类似题先问：命题人想考我“排序与查找的复杂度权衡”还是“二分适用条件”？