GESP 五级 · GESP 202309 C++ 五级 第 19 题

在 C++ 中，可以使用二分查找链表中的元素。

拿到题先想：二分查找的核心操作是什么？它依赖数据结构的什么特性？链表能支持这个特性吗？

很多学生看到'二分'就条件反射选'正确'，完全忽略了算法和数据结构是绑定的。链表不支持随机访问是铁律，这个知识点比算法本身更重要。命题人故意不写'数组'二字，就是测试对数据结构本质属性的理解。如果只背名词，就会掉进这个坑。

1. 这道题考什么

GESP 五级数据结构与算法模块。命题人卡住的是学生死记二分查找却忽略数据结构特性——绝大多数人看到'二分'就条件反射选对，完全没意识到算法和数据结构是绑定的。

2. 概念与核心矛盾

二分查找的核心操作是'随机访问中间节点'，而链表只能顺序遍历。要找到中间位置必须从头走到头再走回来，定位中间本身就要 O(n) 步。这样每次二分要 O(n)，总共 O(n log n)，比 O(n) 线性遍历还慢。所以链表上不能二分，只能线性查找。