c - 是否可以将二进制搜索应用于链接列表以查找元素?

标签 c linked-list binary-search

我读到一个问题,是否可以在链接列表上应用二进制搜索?

由于链接列表不允许随机访问,这看起来几乎不可能。

有没有人有办法做到这一点?

最佳答案

主要问题是,除了您无法对链表元素进行恒定时间访问外,您还没有关于列表长度的信息。在这种情况下,您根本无法将列表“切成两半”。

如果您至少对链表长度有限制,那么问题确实可以在 O(log n) 中解决,并且确实可以使用跳表方法。否则没有什么可以让您免于阅读整个列表,因此 O(n)。

因此,假设链表已排序,并且您知道它的长度(或至少知道最大长度),是的,可以在链表上实现某种二分搜索。不过,这种情况并不常见。

关于c - 是否可以将二进制搜索应用于链接列表以查找元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7645785/

相关文章:

c - struct itimerspec 作为 timer_create 的参数无效参数

c - 读入缓冲区时内存泄漏

java - 在服务器端使用静态 LinkedList 安全吗?

python - 为什么此链接列表代码在 HackerRank 中显示错误?

algorithm - 在二进制搜索中计算中间值

java - 将二进制搜索与带重复项的排序数组一起使用

c - C 中的位域

c - 为什么我的 C 代码打印 Segmentation fault : 11?

java - 使用双向链表的哨兵方法

python - 在 Python 中,使用二分法在字典列表中查找项目