我們知道當一個算法的循環次數每次減少一半時，時間複雜度通常會變成 是 ${O(logn)}$ ，我們可以用二分查找算法作為示例來推算這個時間複雜度的計算過程。

問題背景

假設我們有一個有序數組，我們要在這個數組中查找一個特定的元素。如果元素存在，我們返回其索引；否則返回 -1。

算法步驟

1. 比較目標值與數組的 中間元素。
2. 如果目標值等於中間元素，返回其索引。
3. 如果目標值小於中間元素，則在左半部分繼續查找。
4. 如果目標值大於中間元素，則在右半部分繼續查找。
5. 重複上述步驟，直到找到目標值或者子數組為空。

每次查找時，數組的大小減少一半。

時間複雜度分析

• 第一次查找時，數組的大小是 n。
• 第二次查找時，數組的大小是 n/2。
• 第三次查找時，數組的大小是 n/4。

這樣下去，每次查找數組的大小都會減半。

假設我們進行了 ${K}$ 次查找後，數組的長度 length 變為 1。

因此我們可以得到下列等式

$$ n\times\left(\frac12\right)^k=1 $$

解這個方程：

$$ n\times\left(\frac12\right)^k=1 $$

兩邊同時 除以 n 得：

$$ \left(\frac12\right)^k=\frac1n $$

然後，對兩邊取對數（以2為底）：

$$\log_2 \left( \left( \frac{1}{2} \right)^k \right) = \log_2 \left( \frac{1}{n} \right)$$

根據對數的冪法則 $${\log_b(a^c) = c \log_b(a)}$$ 我們有下面變式：

$$ k \log_2 \left( \frac{1}{2} \right) = \log_2 \left( \frac{1}{n} \right) $$

因為 $${\log_2 \left( \frac{1}{2} \right) = -1}$$ 所以：

$$ k \times (-1) = \log_2 \left( \frac{1}{n} \right) $$

由於 $${\log_2 \left( \frac{1}{n} \right) = -\log_2(n)}$$, 所以：

$$-k = -\log_2(n)$$

$$ k = \log_2(n) $$

因此，二分查找算法在最壞情況下需要 $${\log_2(n)}$$ 次迭代，這就是其時間複雜度為 $${O(\log n)}$$ 的原因