在排序数组中进行二分查找

Question

我刚开始学习一些基本算法，但二分查找算法有些令我困惑。

据我所知，二分查找的最大时间复杂度为O(log(n))，其中log以2为底。

然而，当对非2的幂次方的N值使用公式时，会得到一个非整数值。

我困惑的是：如果最终得到3.3这样的值，那么最多需要3步还是4步。

当使用n = 10的数组时，你会得到3.3的值。话虽如此，我手动计算了步数，得到了4，因此我认为应该向上取整。

但在我的教科书中，它说当n = 10000时，至多需要13个步骤。将其代入上述对数公式后，我们得到13.2，也就是说在这种情况下我们向下取整。

我已经尝试用不同大小的数组进行二分查找，并发现了必须向下取整才能得到教科书答案的情况，也发现了必须向上取整的情况。

我不确定何时向上取整或向下取整，或者我是否犯了其他错误。

如果有人能给我提供一个示例，请使用大小为100000的数组。因为在书中说最多16次，但当我手动将100000减半直到得到1时，我得到了17次。

预先感谢！

- Arkash Vijayakumar

Answer 1

让我们以10为例，先学会走再跑。假设数组是[2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000]，我们要查找3000。

1. 还剩下10个元素。比较50，向右移动。
2. 还剩下5个元素。比较500，向右移动。
3. 还剩下2个元素。比较1000，向右移动。
4. 只剩下1个元素。比较2000，向右移动（或决定“未找到”）。

这样就进行了4次比较。所以，是的，你需要四舍五入，因为你不能免费进行“部分步骤”，有时候你会很幸运，步骤会更少，比如上面的例子，如果你搜索1，它只需要3次比较（50，5，2），假设对于长度为偶数的组，将索引朝左舍入。

- John Zwinck

Answer 2

最坏情况的公式为，换句话说，你需要加一并向下取整。参见https://en.wikipedia.org/wiki/Binary_search_algorithm#Performance

但是在我的教科书中，它说n=10000时，数组最多需要13步。

你的教科书是错误的。对于一个有10000个元素的数组进行二分查找最多需要14步，就像你所期望的那样。

在每一步中，数组大小都会减少一半。 因此，步骤如下： 10000、5000、2500、1250、625、312、156、78、39、19、9、4、2、1。 正如你所看到的，这是14步。

由于书中说最多16次，但当我手动将100000除以2直到得到1时，我得到了17次

你是正确的，这本书是错的。

- merlyn