二分查找问题
对于二分查找，在文件中查找记录所需的平均比较次数是多少？
For binary search, what is the average number of comparisons needed to find a record in a file?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
对于二分查找，在文件中查找记录所需的平均比较次数是多少？
For binary search, what is the average number of comparisons needed to find a record in a file?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（1）
我假设这是家庭作业，所以我将提供提示而不是直接答案。我还假设您被要求找到一个相对准确的答案，而不仅仅是一个大O答案。
可以这样想：每次进行比较时，搜索空间都会减半。如果搜索空间的大小为 S，则在下一次迭代中找到记录的概率为 1/S。如果 C 表示比较次数，则 P(在比较 C 中找到它) = P(在 < C 比较中找不到它) * P(在比较 C 上找到它 | 在 < C 比较中找不到它）。
I'm assuming this is homework, so I'll provide a hint instead of a straight-up answer. I'll also assume you've been asked to find a relatively exact answer, not just a big-O answer.
Think of it this way: Every time you do a comparison, you halve the search space. If the search space is of size S, then the probability of finding the record on the next iteration is 1/S. If C denotes the number of comparisons, then P(find it on comparison C) = P(don't find it in < C comparisons) * P(find it on comparison C | don't find it in < C comparisons).