blocks|key|1368874|text|对于简单的单链表，这肯定是不可能的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1368875|草图证明:为了检查单链表的最后一个节点，我们必须通过归纳来执行跟随“k%2B1”指针证明的n-1操作，因为只有一个引用指向k%2B1的th节点，并且它在k的th节点中，并且需要一个操作来跟随它。对于某些输入，有必要检查最后一个节点(具体地说，如果搜索的元素等于或大于它的值)。因此，对于某些输入，所需时间与n成正比。|offset|length|style|CODE|1368876|您要么需要更多时间，要么需要不同的数据结构。|1368877|请注意，您可以使用二进制搜索在O(log+)比较中完成此操作。这只会花费更多的时间，所以只有在比较比列表遍历开销大得多的情况下，这个事实才是有意义的。|1368878|entityMap^0|0|Y|3|17|3|1N|3|20|1|45|1|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@$D|P|E|Q|F|G]|$D|R|E|S|F|G]|$D|T|E|U|F|G]|$D|V|E|W|F|G]|$D|X|E|Y|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|Z|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|10|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|11|8|@]|9|@]|A|$]]]|M|$]]

It is certainly not possible with a plain singly-linked list.

Sketch proof: to examine the last node of a singly-linked list, we must perform <code>n-1</code> operations of following a "next" pointer [proof by induction on the fact that there is only one reference to the <code>k+1</code>th node, and it is in the <code>k</code>th node, and it takes a operation to follow it]. For certain inputs, it is necessary to examine the last node (specifically, if the searched-for element is equal to or greater than its value). Hence for certain inputs, time required is proportional to <code>n</code>.

You either need more time, or a different data structure.

Note that you can do it in O(log n) comparisons with a binary search. It'll just take more time than that, so this fact is only of interest if comparisons are very much more expensive than list traversal.

blocks|key|2034372|text|您需要使用skip+list。这对于普通的链表来说是不可能的(我真的很想知道普通链表是否可以做到这一点)。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2034373|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Skip_list^0|5|9|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

You need to use <a href="http://en.wikipedia.org/wiki/Skip_list" rel="noreferrer">skip list</a>. This is not possible with a normal linked list (and I really want to learn if this is possible with normal list).

blocks|key|3435769|text|在链表中，二分查找的复杂度可能不是O(log+)，但通过使用双指针方法可以实现最小的复杂度，如本文所述：http://www.ijcsit.com/docs/Volume%25205/vol5issue02/ijcsit20140502215.pdf|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|3435770|entityMap|0|LINK|mutability|MUTABLE|url|http://www.ijcsit.com/docs/Volume%25205/vol5issue02/ijcsit20140502215.pdf^0|1G|1Z|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

In Linked List, binary search may not achieve a complexity of O(log n) but least can be achieved a little by using Double Pointer Method as described here in this research work: <a href="http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf" rel="nofollow">http://www.ijcsit.com/docs/Volume%205/vol5issue02/ijcsit20140502215.pdf</a>

blocks|key|1368988|text|如前所述，这在一般情况下是不可能的。但是，在像C这样的语言中，如果列表节点是连续分配的，则可以将结构视为节点数组。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1368989|显然，这只是这个问题的刁钻的问题变体的一个答案，但这个问题总是不可能的或者是刁钻的问题。|1368990|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

As noted, this is not in general possible. However, in a language like C, if the list nodes are contiguously allocated, it would be possible to treat the structure as an array of nodes. 

Obviously, this is only an answer to a trick question variant of this problem, but the problem is always an impossibility or a trick question.

blocks|key|3435873|text|是的，在java语言中是可能的，如下所示。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3435874|Collections.<T>binarySearch(List<T>+list,+T+key)|code-block|syntax|javascript|3435875|用于在任何List上进行二进制搜索。它可以在ArrayList、LinkedList和任何其他List上运行。|offset|length|style|CODE|3435876|entityMap^0|0|0|5|4|M|9|W|A|1B|4|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@$I|R|J|S|K|L]|$I|T|J|U|K|L]|$I|V|J|W|K|L]|$I|X|J|Y|K|L]]|9|@]|A|$]]|$1|M|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|N|$]]

Yes, it is possible in java language as below..

<pre><code>Collections.&lt;T&gt;binarySearch(List&lt;T&gt; list, T key)
</code></pre>

for binary search on any <code>List</code>. It works on <code>ArrayList</code> and on <code>LinkedList</code> and on any other <code>List</code>.

blocks|key|5035723|text|使用映射创建链接列表。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5035724|Map+M，M第一element=second元素，M第二element=third元素，|5035725|..。|5035726|5035727|这是一个链表...|5035728|但因为这是一张地图。|5035729|它在内部使用二进制搜索来搜索任何元素。|5035730|任何元素的搜索都需要O(log+)|5035731|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|S|8|@]|9|@]|A|$]]|$1|F|3|E|5|6|7|T|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|V|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|W|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|X|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|P|$]]

Use MAPS to create LINK LISTS. 
Map M , M[first element]=second element , M[second element]=third element , 
... 
... 
its a linked list... 
but because its a map... 
which internally uses binary search to search any element.. 
any searching of elements will take O(log n)

Recently I came across one interesting question on linked list. Sorted singly linked list is given and we have to search one element from this list. 

Time complexity should not be more than <code>O(log n)</code>. This seems that we need to apply binary search on this linked list. How? As linked list does not provide random access if we try to apply binary search algorithm it will reach O(n) as we need to find length of the list and go to the middle.

Any ideas?

how to apply binary search O(log n) on a sorted linked list?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

最近，我遇到了一个关于链表的有趣问题。给出了排序的单链表，我们必须从这个链表中搜索一个元素。时间复杂度不应超过O(log n)。这似乎需要我们在这个链表上应用二进制搜索。多么?由于链表不提供随机访问，如果我们尝试应用二进制搜索算法，它将达到O(n)，因为我们需要找到链表的长度并进入中间。有什么想法吗？

问如何在排序链表上应用二进制搜索O(log )？
EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在排序链表上应用二进制搜索O(log )？EN

回答 6

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在排序链表上应用二进制搜索O(log )？
EN