GESP 五级 · GESP 202606 C++ 五级 第 22 题

二分查找不仅可以应用于有序数组，也可以在不增加时间复杂度的情况下应用于有序的单链表，因为链表也支持 $O(1)$ 时间内的随机访问。

链表不支持随机访问，不能进行二分查找。二分查找要求数据结构支持O(1)的随机访问（如数组）。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】二分查找｜单链表｜随机访问

1. 🎯 考纲定位

GESP 五级《数据结构与算法》模块。命题人想卡住"链表不支持 O(1) 随机访问"这一核心认知，很多考生只记"有序就能二分"却忽略访问代价。