通过多个元素进行二分查找

Question

我在考试中遇到了这个问题，

我有一台非常慢的计算机，它需要一秒钟的时间来对具有 1,000（一千）个元素的数组进行二进制搜索。我应该期望计算机对具有 1,000,000（一百万）个元素的数组进行二进制搜索需要多长时间？

我很难理解这一点，搜索 100 万个元素会比搜索 1,000 个元素花费的时间更长吗？还是取决于计算机？

Answer 1

这确实取决于计算机，也取决于数组的大小。由于这道题用的是同一台电脑，所以我们可以抽象出电脑的效果，关注样本量。

二分查找有对数time complexity。如果您比较 log(1_000) 和 log(1_000_000) 之间的差异，您会发现在 100 万个元素数组中搜索的时间应该翻倍（2 秒）。

这是假设最坏的情况。对于一般情况，计算会变得更加复杂，您可以查看this wikipedia page进行更深入的分析。

Answer 2

首先，二进制搜索需要对列表或数组进行排序。由于您将每个 list/sublist 分成两半，因此需要 log2(N) 次搜索才能找到正确的项目，其中 log2 记录到 base 2.

因此对于 1_000_000 项，它应该只需要 20 comparisons 就可以找到该项目。所以它应该非常快（没有开始对列表进行排序的时间）。

1000 项大约需要 10 comparisons。在任何现代处理器上进行如此简单的搜索，imo，一秒钟都太长了。

Answer 3

二分查找有O(log(N))时间复杂度，完成时间为

t = c * log(N, 10)

在 N = 1000 的给定情况下，我们知道 t，因此我们可以找出 c

1 = c * log(1000, 10) 

1 = c * 3

c = 1/3

对于N = 1000000，我们有

t = 1 / 3 * log(1000000, N) =
  = 1 / 3 * 6 = 
  = 2

因此我们可以预期 1000000 项内的二分查找将在 2 秒内完成。

请注意 O(log(N)) == O(log(N, m)) 因为 log(N, m) == log(N, k) / log(m, k)，这意味着在使用 O(log(N)) 时我们可以自由选择对数底数。在我们的例子中（1000 和 1000000）使用基数 10（或 1000）

很方便

通过多个元素进行二分查找

Binary Search through multiple elements

algorithm

binary-search

time-complexity