GESP 六级 · GESP 六级样题（C++ 组） 第 24 题

将 $N$ 个数据按照从小到大顺序存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是 $O(log N)$。（ ）

这道题其实是在考你对数据结构底层特性的理解。拿到题别急着套公式，先问自己：二分查找最核心依赖的是什么？是随机访问。链表能随机访问吗？不能。所以它的平均复杂度肯定不是对数级，而是退化成线性了。

很多考生一看到‘二分查找’四个字就条件反射选‘O(log N)'，完全忽略了前提条件。还有人会纠结‘单向’还是‘双向’，觉得双向链表能取中间节点是不是就能二分，其实双向链表依然只能顺序遍历，无法跳跃，所以无论单向还是双向，链表上的二分查找都跑不出 O(log N)。

【考点】单向链表结构特性｜二分查找随机访问前提｜算法时间复杂度分析

1. 考纲定位

GESP 六级 C++ 组「数据结构与算法」模块，第 6 级要求掌握链表基本操作与算法复杂度分析。命题人卡住的是考生对链表随机访问能力的认知盲区，很多人误以为链表也能像数组一样支持任意位置访问。