二分查找不能用于链表结构的主要原因在于**无法实现随机访问*

一、顺序查找
平均查找长度（ASL）：

• 等概率成功查找时，ASL 为(n+1)/2(n+1)/2(n+1)/2（约表长的一半）；
• 查找失败时，需比较n+1n+1n+1次。

优化策略：若各结点查找概率不等，将高概率元素前置（按查找概率从大到小排列），可降低平均查找长度，提高效率。

优缺点：

• 优点：算法简单，适用于任意存储结构（向量或链表），对数据是否有序无要求；
• 缺点：效率低，时间复杂度为O(n)O(n)O(n)，当nnn较大时性能差，不适合大规模数据查找。

二、二分法查找（折半查找）
适用条件：

• 表必须是有序表（关键字有序）；
• 存储结构为顺序存储结构（如数组），以支持随机访问。

核心步骤：

1. 初始化查找区间：low = 0，high = n-1；
2. 当low <= high时，计算中点：mid = ⌊(low + high) / 2⌋；
3. 比较待查值kkk与R[mid].keyR[mid].keyR[mid].key：
   • 若R[mid].key>kR[mid].key > kR[mid].key>k，则在左半区间继续查找：high = mid - 1；
   • 若R[mid].key<kR[mid].key < kR[mid].key<k，则在右半区间继续查找：low = mid + 1；
   • 若相等，则查找成功，返回位置mid；
4. 若low > high，查找失败，返回失败标志。

性能分析：

• 成功查找的 ASL 约为log⁡2(n+1)−1\log_2(n+1) - 1log2​(n+1)−1；
• 时间复杂度为O(log⁡n)O(\log n)O(logn)，效率远高于顺序查找；
• 缺点：依赖有序表和顺序存储，插入删除困难，适用于静态查找表。、
  二分查找不能用于链表结构的主要原因在于无法实现随机访问。

二分查找的核心是每次通过计算中点位置mid，直接访问中间元素R[mid]R[mid]R[mid]，从而将查找区间缩小一半。这种操作要求能在O(1)O(1)O(1)时间内访问任意位置的元素，这只有在顺序存储结构（如数组）中才能实现。

而链表是一种链式存储结构，其特点是：

• 元素在内存中非连续存放；
• 只能从头结点开始，逐个遍历才能访问到第midmidmid个元素；
• 访问中间元素的时间复杂度为O(n)O(n)O(n)，而非O(1)O(1)O(1)。

因此，在链表上进行二分查找时，每次计算mid后仍需花费O(n)O(n)O(n)时间去遍历到该位置，导致整体时间复杂度退化为O(nlog⁡n)O(n \log n)O(nlogn)，甚至更差，失去了二分查找高效性的优势。

此外，频繁的中点定位会使算法效率远低于直接使用顺序查找。

✅ 虽然可以通过“跳表”或“双向链表+索引”等方式近似实现类似二分的查找，但这些已不属于传统意义上的二分查找。