开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >二分搜索问题

问二分搜索问题
EN

Stack Overflow用户

提问于 2010-03-09 11:21:03

回答 1查看 296关注 0票数 2

对于二进制搜索，在文件中查找记录所需的平均比较次数是多少？

EN

回答 1

Stack Overflow用户

发布于 2010-03-09 11:29:25

我假设这是作业，所以我将提供一个提示，而不是一个直接的答案。我还假设你已经被要求找到一个相对准确的答案，而不仅仅是一个大O的答案。

可以这样想:每次进行比较时，搜索空间都会减半。如果搜索空间的大小是S，那么在下一次迭代中找到记录的概率是1/S。如果C表示比较的次数，那么P(在比较C中找到它)=P(不在

票数 2

EN

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/2406417

复制

相似问题