是否可以对链接列表应用二分搜索来查找元素？
我读过一个问题，是否可以在链接列表上应用二分搜索？
由于链接列表不允许随机访问，这看起来几乎是不可能的。
有人有办法做到吗？
I have read a question ,is it possible to apply binary search on a link list?
Since link list doesn't allow random access, this looks practically impossible.
Any one has any way to do it?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
除了无法恒定时间访问链表元素之外，主要问题是您没有有关列表长度的信息。在这种情况下，您根本无法将列表“切成”两半。
如果链表长度至少有一个界限，那么实际上可以使用跳表方法在 O(log n) 内解决问题。否则，没有什么可以阻止你阅读整个列表，因此 O(n)。
因此，假设链表已排序，并且您知道其长度（或至少知道最大长度），是的，可以在链表上实现某种二分搜索。但这种情况并不常见。
The main issue, besides that you have no constant-time access to the linked list elements, is that you have no information about the length of the list. In this case, you simply have no way to "cut" the list in 2 halves.
If you have at least a bound on the linked list length, the problem is solvable in O(log n), with a skip list approach, indeed. Otherwise nothing would save you from reading the whole list, thus O(n).
So, assuming that the linked list is sorted, and you know its length (or at least the maximum length), yes it's possible to implement some sort of binary search on a linked list. This is not often the case, though.
对于普通链表，您不能直接进行二分查找，因为链表上的随机访问是 O(n)。
如果您需要快速搜索，树状数据结构（R/B 树、trie、堆等）提供了链表的许多优点（相对便宜的随机插入/删除），同时搜索非常高效。
With a plain linked list, you cannot do binary search directly, since random access on linked lists is O(n).
If you need fast search, tree-like data structures (R/B tree, trie, heap, etc.) offer a lot of the advantages of a linked list (relatively cheap random insertion / deletion), while being very efficient at searching.
由于您所说的原因，不使用经典链表。
但有一种结构确实允许从链接列表派生的二分搜索形式： 跳过列表。
（这实施起来并不简单。）
Not with a classic linked list, for the reasons you state.
But there is a structure that does allow a form of binary search that is derived from linked lists: Skip lists.
(This is not trivial to implement.)
我曾经为包含排序键的单链表实现过类似的东西。我需要在其中找到几个键（一开始只知道其中一个，其余的都依赖于它）并且我想避免一次又一次地遍历列表。而且我不知道列表的长度。
所以，我最终这样做了...我创建了 256 个指向列表元素的指针，并使它们指向前 256 个列表元素。一旦使用了所有 256 个指针并且需要第 257 个指针，我就删除了奇数指针值（1、3、5 等），将偶数指针值（0、2、4 等）压缩到前 128 个指针中并继续将剩余的一半 (128) 指针分配给其余的指针，这次跳过所有其他列表元素。重复这个过程直到列表末尾，此时这些指针指向整个列表中均匀分布的元素。然后，我可以使用这 256 个（或更少）指针进行简单的二分搜索，将线性列表搜索缩短到原始列表长度的 1/256（或 1/what-th）。
这不是很花哨或强大，但有时只需更改少量代码即可实现足够的性能改进。
I have once implemented something like that for a singly-linked list containing sorted keys. I needed to find several keys in it (knowing only one of them at the beginning, the rest were dependent on it) and I wanted to avoid traversing the list again and again. And I didn't know the list length.
So, I ended up doing this... I created 256 pointers to point to the list elements and made them point to the first 256 list elements. As soon as all 256 were used and a 257th was needed, I dropped the odd-numbered pointer values (1,3,5,etc), compacted the even-numbered (0,2,4,etc) into the first 128 pointers and continued assigning the remaining half (128) of pointers to the rest, this time skipping every other list element. This process repeated until the end of the list, at which point those pointers were pointing to elements equally spaced throughout the entire list. I then could do a simple binary search using those 256 (or fewer) pointers to shorten the linear list search to 1/256th (or 1/whatever-th) of the original list length.
This is not very fancy or powerful, but sometimes can be a sufficient perf improvement with minor code changes.
您可以在链接列表上进行二分搜索。正如您所说，您没有随机访问权限，但您仍然可以从列表的开头或其他位置开始找到具有特定索引的元素。因此，直接的二分搜索是可能的，但与数组的二分搜索相比速度较慢。
如果您有一个列表，其中比较比简单的列表遍历要昂贵得多，那么对于适当大小的列表，二分搜索将比线性搜索便宜。线性搜索需要
O(n)次比较和O(n)节点遍历，而二分搜索则需要O(log n)次比较和O(n log n)节点遍历。我不确定这个O(n log n)界限是否紧密，其他的都是。You can do a binary search on a linked list. As you say, you don't have random access, but you can still find the element with a specific index, starting either from the start of the list or from some other position. So a straightforward binary search is possible, but slow compared with binary search of an array.
If you had a list where comparisons were much, much more expensive than simple list traversal, then a binary search would be cheaper than a linear search for suitably-sized lists. The linear search requires
O(n)comparisons andO(n)node traversals, whereas the binary search requiresO(log n)comparisons andO(n log n)node traversals. I'm not sure if thatO(n log n)bound is tight, the others are.据我所知，没有办法以二分搜索的方式搜索链表。在二分查找中，我们通常会找到数组的“中间”值，这对于列表来说是不可能的，因为列表是我们必须严格使用“开始”（指向列表第一个节点的节点）来遍历任何一个的结构。我们的列表元素。
在数组中，我们可以使用 INDEX 转到特定元素，这里没有索引问题（由于链表中的随机访问不可用）。
所以，我认为在通常的实践中，二分查找是不可能用链表实现的。
According to me, there is no way to search the Linked list in binary search manner. In binary search, we usually find out 'mid' value of array which is impossible with lists, since lists are the structure where we have to strictly use the 'start' (Node pointing to very 1st node of list) to traverse to any of our list elements.
And in array, we can go to specific element using INDEX, here no question of Index (Due to Random Access unavailability in linked lists).
So, I think that binary search is not possible with linked list in usual practices.
为了在链表上应用二分搜索，您可以维护一个变量 count，它应该迭代链表并返回节点总数。此外，您还需要在节点类中保留一个 int 类型的 INDEX 变量，该变量应该在创建每个新节点时递增。之后，您将很容易将链表分成两半并对其应用二分搜索。
for applying binary search on linked list, you can maintain a variable count which should iterate through the linked list and return the total number of nodes. Also you would need to keep a var of type int say INDEX in your node class which should increment upon creation of each new node. after which it will be easy for you to divide the linked list in 2 halves and apply binary search over it.