binary-search - binary search question

Question

For binary search, what is the average number of comparisons needed to find a record in a file?

Answer 1

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

可以这样想：每次进行比较时，搜索空间都会减半。如果搜索空间的大小为 S，则在下一次迭代中找到记录的概率为 1/S。如果 C 表示比较次数，则 P（在比较 C 中找到它）= P（在 < C 比较中找不到它）* P（在比较 C 中找到它 | 在 < C 比较中找不到它）。