我读过一个问题，是否可以在链接列表上应用二进制搜索?
由于链表不允许随机访问，这看起来几乎是不可能的。
谁有办法做这件事?
主要的问题是，除了您没有固定时间访问链表元素之外，您没有关于链表长度的信息。在这种情况下，你根本没有办法把列表"切"成两半。
如果你在链表长度上至少有一个界限，那么这个问题是在O(log n)内解决的，用跳跃表的方法，确实。否则没有什么可以避免你阅读整个列表，因此O(n)。
所以，假设链表是排序的，并且你知道它的长度(或者至少是最大长度)，是的，可以在链表上实现某种形式的二分查找。但这种情况并不常见。
对于普通链表，您不能直接进行二进制搜索，因为对链表的随机访问是O(n)。
如果您需要快速搜索，树状数据结构(R/B树，树，堆等)提供了链表的许多优点(相对便宜的随机插入/删除)，同时在搜索方面非常高效。
由于你所说的原因，不能使用经典的链表。
但是有一种结构确实允许从链表派生出一种形式的二分查找:跳跃表。
(这是不容易实现的)
我曾经为一个包含排序键的单链表实现过类似的东西。我需要在列表中找到几个键(一开始只知道其中一个键，其余的都依赖于它)，我希望避免一次又一次地遍历列表。而且我不知道列表的长度。
所以，我最终做了这个…我创建了256个指针指向列表元素，并让它们指向前256个列表元素。当所有256个指针都被使用完并且需要第257个指针时，我删除了奇数指针值(1,3,5等)，将偶数指针值(0,2,4等)压缩到前128个指针中，并继续将剩下的一半(128)指针赋值给其余的指针，这一次跳过了所有其他列表元素。这个过程一直重复到列表的末尾，此时这些指针指向整个列表中间隔相等的元素。然后，我可以使用256个(或更少)指针进行简单的二进制搜索，以将线性列表搜索缩短为原始列表长度的1/256(或1/任意th)。
这不是很花哨，也不是很强大，但有时可以通过对代码进行微小的更改来充分提高性能。
您可以在链表上进行二分查找。正如您所说，您没有随机访问，但您仍然可以找到具有特定索引的元素，从列表的开始或从其他位置开始。因此，直接的二分查找是可能的，但与对数组的二分查找相比，速度较慢。
如果你有一个列表，其中比较比简单的列表遍历要昂贵得多，那么对于合适大小的列表，二进制搜索将比线性搜索便宜。线性搜索需要O(n)比较和O(n)节点遍历，而二分搜索需要O(log n)比较和O(n log n)节点遍历。我不确定是否O(n log n)绑定是紧的，其他的。
据我所知，没有办法以二进制搜索的方式搜索链表。在二进制搜索中，我们通常会找到数组的"中间"值，这在列表中是不可能的，因为列表是一种结构，我们必须严格使用"开始"(节点指向列表的第一个节点)来遍历列表中的任何元素。
在数组中，我们可以使用INDEX去到特定的元素，这里没有索引的问题(由于链表中的随机访问不可用)。
所以，我认为在通常情况下，用链表进行二分查找是不可能的。
对于在链表上应用二进制搜索，您可以维护一个变量计数，它应该遍历链表并返回节点总数。此外，您还需要在节点类中保留一个int类型的变量，例如INDEX，该变量应在创建每个新节点时增加。之后，您将很容易将链表分成两半，并对其应用二进制搜索。