algorithm - 二分查找的时间复杂度

Question

我是编码新手，目前正在学习搜索/排序算法。目前，我正在研究二进制搜索，并且很难理解最坏情况下 O(log2 n) 的时间复杂度。有人可以向我清楚地解释如何进行以便我知道逻辑吗？ (一步一步)

伪代码如下:

binarySearch( list, value, low, high ){ 

  if low <= high { 
     mid = (low + high)/ 2

     if value == list[mid]
         return mid

      else if value < list[mid]
         return binarySearch( list, value, low, mid - 1 )

      else
          return binarySearch( list, value, mid+1, high)
      } 

  else
  return -1 
}

Answer 1

概览

暂时忘掉你的代码，看看纸上的算法，通过一些例子运行它，看看一些可视化，直到你真正理解它。

看看我从 Wikipedia 偷来的这张插图:

搜索范围在每一轮中有效减半。所以你在最近的 log_2(n) 步骤中找到了这个数字。

---

猜一个数字

您可能熟悉“猜数字游戏”。游戏是这样的

Think of a number between 0 and 100 but do not tell me the answer yet.

Now, I will try to guess the number and all you can say is:

• yes, correct answer
• no, the number is too high
• no, the number is too low

这个游戏的最佳策略是二分查找。让我们快速玩一遍，您会更好地理解。

第一个猜测将是 50，因为它位于当前搜索范围 [0, 100] 的中间。我可能会说 50 现在太高了。这有效地将搜索范围减半到 [0, 49]，下一个猜测将是 25。

[0, 100], is it 50?
> too high

[0, 49], is it 25?
> too low

[26, 49], is it 38?
> too high

[26, 37], is it 32?
> too high

[26, 31], is it 28?
> too high

[26, 27], is it 27?
> too high

[26], is it 26?
> correct!

你刚刚见证了最坏的情况，所有的猜测都错了，直到只剩下 26 个。我们通过 7 个步骤找到了解决方案。 log_2(100) = 6.64...，所以这听起来是正确的。

---

那么为什么是 log_2？

现在你应该明白搜索范围在每一步都会减半。那么，为什么这会在数学上导致 log_2？

其实很简单。您多久可以将一个数字除以 2 直到小于等于 1？ log_2 次。换句话说，搜索范围何时从 n 数字下降到仅 1 数字 - 恰好 ¹ log_2(n) 步骤。

<子>1。从技术上讲，您必须将其四舍五入，因为没有“步骤的分数”，所以 ceil(log_2(n))，但这并不重要。

请注意，由于 Big-O 在数学上的定义方式，O(log_2(n)) 和 O(log(n)) 表示相同的集合。因此，您通常只会看到 O(log(n))(没有 2)被指定为二分查找的时间复杂度。

---

代码

最后，让我们看一下您的伪代码，并说服自己这实际上与我们刚刚在“猜数字”游戏中使用的策略相同。

您有列表，low, high 表示搜索范围。第一步，选择中间的值:

mid = (low + high) / 2

例如，在之前的游戏中，[0, 100] 如何导致最初猜测 50，等等。

现在，您有了实际的猜测，查找:

if value == list[mid]

根据它是更高还是更低，您可以通过使用更小的搜索范围再次调用该方法来将搜索范围减半。即要么与

• low, mid - 1，如果数字太高，
• 或 mid + 1, high，如果数字太低。

在游戏中，根据 50 太高或太低。