我读到一个问题,是否可以在链接列表上应用二进制搜索?
由于链接列表不允许随机访问,这看起来几乎不可能。
有没有人有办法做到这一点?
最佳答案
主要问题是,除了您无法对链表元素进行恒定时间访问外,您还没有关于列表长度的信息。在这种情况下,您根本无法将列表“切成两半”。
如果您至少对链表长度有限制,那么问题确实可以在 O(log n) 中解决,并且确实可以使用跳表方法。否则没有什么可以让您免于阅读整个列表,因此 O(n)。
因此,假设链表已排序,并且您知道它的长度(或至少知道最大长度),是的,可以在链表上实现某种二分搜索。不过,这种情况并不常见。
关于c - 是否可以将二进制搜索应用于链接列表以查找元素?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7645785/