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，即做出的决策数。

最后，你可能会问，如果我使用以 2 为底的 log，为什么像你那样写成以 10 为底的 log 也可以呢？基数并不重要，因为差异是 only a constant factor它被大 O 表示法“忽略”。

平均情况

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

1. 第一次尝试时只能找到数组中的一个元素。
2. 第二次尝试时只能找到两个元素。 (因为第一次尝试后，我们要么选择了右半部分，要么选择了左半部分。)
3. 第三次尝试时只能找到四个元素。

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

1. 一半的元素需要进行最大数量的决策才能找到。
2. 四分之一的元素需要更少的决策才能找到。
3. 等等

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