我在 python 中使用谷歌搜索二进制搜索，我发现了这个: http://openbookproject.net/thinkcs/python/english3e/list_algorithms.html
表示max之间的一般关系。迭代次数(与 Probe 相同，对吗？)和 N(列表大小)由 N = 2^k -1 给出，其中 k 是最大迭代次数。
但是根据我的理解，一般关系不应该是 N = 2^k
每次搜索后，我们都会将列表除以 2，直到得到 1。
因此最大迭代次数是log2 N而不是log2 (N+1)
我用谷歌搜索了一下，发现一个网站支持我的回答，但没有太多解释。 (链接在这里:http://codingexplained.com/coding/theory/binary-search-algorithm)
有人可以解释一下它背后的数学原理吗？谢谢。
最佳答案
设 P(n) 为 n 元素所需的探测数。那么我们可以写出下面的等式:
P(0) = 0
P(n) = 1 + P((n-1)/2)
解释:
首先我们没有元素——无事可做。
然后我们做 1 次探测，剩下 (n-1)/2 元素(我们扔掉 1 因为我们刚刚检查了它)所以我们需要做 P((n- 1)/2) 更多。
此等式的 P(n) 的结果将是 floor(lg(n+1))。您可以查看一些示例(例如 n=6 和 n=7)，或者您可以阅读如何求解递归方程
关于Python 二进制搜索(最大迭代次数)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35114640/