一個 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

結論

當面對連續的劃分（無論是兩個還是任何數字）時，請記住複雜性是對數的。