一个 O(log n)的例子

介绍

请考虑以下问题：

L 是一个包含 n 有符号整数的排序列表（n 足够大），例如 [-5, -2, -1, 0, 1, 2, 4]（这里，n 的值为 7）。如果已知 L 包含整数 0，那么如何找到 0 的索引？

天真的方法

首先想到的是只读取每个索引，直到找到 0。在最坏的情况下，操作次数是 n，因此复杂度为 O(n)。

这适用于 n 的小值，但是有更有效的方法吗？

二分法

考虑以下算法（Python3）：

a = 0
b = n-1
while True:
  h = (a+b)//2 ## // is the integer division, so h is an integer
  if L[h] == 0:
    return h
  elif L[h] > 0:
    b = h
  elif L[h] < 0:
    a = h

a 和 b 是要找到 0 的索引。每次我们进入循环时，我们使用 a 和 b 之间的索引，并使用它来缩小要搜索的区域。

在最坏的情况下，我们必须等到 a 和 b 相等。但这需要多少次操作？不是 n，因为每次我们进入循环时，我们将 a 和 b 之间的距离除以 2。相反，复杂性是 O（log n）。

说明

注意：当我们写 log 时，我们指的是二进制对数，或者 log base 2（我们将写入“log_2”）。由于 O（log_2 n）= O（log n）（你可以进行数学运算），我们将使用 log 而不是“log_2”。

让我们调用 x 操作的数量：我们知道 1 = n /（2 ^ x）。

所以 2 ^ x = n，然后 x = log n

结论

当面对连续的划分（无论是两个还是任何数字）时，请记住复杂性是对数的。