search - 二进制搜索 - 最坏/平均情况

Question

我发现很难理解为什么/如何使用二进制搜索在数组/列表中搜索键的最坏情况和平均情况是 O(log(n))。

log(1,000,000) 只有 6。log(1,000,000,000) 只有 9 - 我明白了，但我不明白其中的解释。如果没有测试，我们怎么知道平均/最坏情况实际上是 log(n)？

我希望你们明白我想说的是什么。如果没有，请告诉我，我会尝试以不同的方式解释。

Answer 1

最坏情况

每次二进制搜索代码做出决定时，它都会从考虑中消除一半的剩余元素。因此，您将每个决定的元素数量除以 2。

在您只剩下一个元素之前，您可以除以 2 多少次？如果n是元素的起始个数，x是你除以2的次数，我们可以这样写:

n/(2 * 2 * 2 * ... * 2) = 1 ['2' 重复 x 次]

或者，等价地，

n/2^x = 1

或者，等价地，

n = 2^x

所以 n 的以 2 为底的对数给你 x，这是正在做出的决定的数量。

最后，您可能会问，如果我使用 log base 2，为什么像您那样将其写为 log base 10 也可以？基数无关紧要，因为差异是 only a constant factor它被大 O 符号“忽略”。

平均情况

我看到你也问了平均情况。考虑:

1. 数组中只有一个元素可以在第一次尝试时找到。
2. 第二次尝试只能找到两个元素。 (因为在第一次尝试之后，我们选择了右半边或左半边。)
3. 第三次尝试只能找到四个元素。

您可以看到模式:1, 2, 4, 8, ... , n/2。表达相同的模式向另一个方向发展:

1. 一半的元素采取最大数量的决定来找到。
2. 四分之一的元素减少了一次查找决定。
3. 等等

由于一半的元素花费的时间最长，因此其他元素花费的时间少多少并不重要。我们可以假设所有元素都花费了最多的时间，即使其中一半实际上花费了 0 时间，无论真实平均值是多少，我们的假设都不会超过两倍。我们可以忽略“double”，因为它是一个常数因子。因此，就大 O 表示法而言，平均情况与最坏情况相同。