摘要訊息 : 針對有序的集合來說, 是否存在比按順序搜尋更快的搜尋方法呢?

目錄 隱藏
0. 前言
1. 二分搜尋
2. 複雜度分析
3. 實作

0. 前言

在《【資料結構】向量 (順序表)》第 4 節中, 我們談到過在一個向量中進行搜尋的操作, 這個操作的時間複雜度為 \Theta(n). 但是如果給出的集合本身是有序的, 我們是否可以降低這個時間複雜度呢?

假如有一本書, 它有兩千頁. 如果要翻到第 1634 頁, 需要多久? 不會有人從第一頁開始一頁一頁翻吧? 一般, 我們翻到 1500 - 1700 頁左右, 然後再慢慢找. 這裡面便體現了二分搜尋的思想.

更新紀錄 :

  • 2022 年 4 月 25 日進行第一次更新和修正.

1. 二分搜尋

對於一個有序的序列 \mathscr {S} = \left \{ e_{1}, e_{2}, ..., e_{n} \right \}, 如果其中存在一個我們想要搜尋的元素 e, 我們從 \mathscr {S} 的中間開始搜尋. 首先查看 e_{\left \lfloor \frac {n}{2} \right \rfloor} 和 e 是否相等. 如果相等, 我們便找到了這個元素在 \mathscr {S} 中的位置. 如果不相等, 就要分為另外兩種情況來處理. 第一種情況是 e < e_{\left \lfloor \frac {n}{2} \right \rfloor}, 此時我們可以捨棄在 e_{\left \lfloor \frac {n}{2} \right \rfloor} 之後的所有元素中進行搜尋, 因為那些元素至少和 e_{\left \lfloor \frac {n}{2} \right \rfloor} 相等, 自然也不會比 e 小. 接下來我們主要在 \mathscr {S}_{\mathrm {L}} = \left \{ e_{1}, e_{2}, ..., e_{\left \lfloor \frac {n}{2} \right \rfloor - 1}, \bcancel {e_{\left \lfloor \frac {n}{2} \right \rfloor}}, \bcancel {e_{\left \lfloor \frac {n}{2} \right \rfloor + 1}}, ..., \bcancel {e_{n}} \right \} 中未被划去的部分進行二分搜尋. 第二種情況是 e > e_{\left \lfloor \frac {n}{2} \right \rfloor}, 類似地, 我們捨棄掉 e_{\left \lfloor \frac {n}{2} \right \rfloor} 之前的元素, 主要在 \mathscr {S}_{\mathrm {R}} = \left \{ \bcancel {e_{1}}, \bcancel {e_{2}}, ...., \bcancel {e_{\left \lfloor \frac {n}{2} \right \rfloor}}, e_{\left \lfloor \frac {n}{2} \right \rfloor + 1}, e_{\left \lfloor \frac {n}{2} \right \rfloor + 2}, ..., e_{n} \right \} 中未被划去的部分進行二分搜尋.

Algorithm 1. 二分搜尋

我們稱 Algorithm 1 為二分搜尋法 (binary serach).

例題 1. 設集合 \mathscr {S} = \left \{ 0, 1, 5, 8, 9, 16, 20, 22 \right \}, 在 \mathscr {S} 使用 Algorithm 1 搜尋 17 所在的位置.

解 :

我們設定 l = 1, r = 8. 首先有 m = \left \lfloor \frac {l + r}{2} \right \rfloor = 4,

Figure 1-1. 第一次搜尋

由於 8 < 17, 所以令 l = m + 1 = 5. 現在再次更新 m = \left \lfloor \frac {l + r}{2} \right \rfloor = 6.

Figure 1-2. 第二次搜尋

由於 16 < 17, 所以令 l = m + 1 = 7. 現在再次更新 m = \left \lfloor \frac {l + r}{2} \right \rfloor = 7.

Figure 1-3. 第三次搜尋

由於 20 > 17, 所以令 r = m - 1 = 6. 現在 l > r, 所以 17 並不在 \mathscr {S} 中, 二分搜尋終止.

\blacksquare

2. 複雜度分析

二分搜尋法所需要的輔助性空間和集合中的元素數量無關, 所以二分搜尋法的空間複雜度為 \Theta(1). 為了得到二分搜尋法的時間複雜度, 我們將 Algorithm 1 使用 C++ 進行描述, 同時改為遞迴的版本 :

int binary_search(int arr[], int left, int right, int value) {
    if(left > right) {      // #1
        return -1;      // #2
    }
    auto middle {(left + right) / 2};       // #3
    if(arr[middle] == value) {      // #4
        return middle;      // #5
    }else if(value > arr[middle]) {     // #6
        return bs(arr, middle + 1, right, value);       // #7
    }
    return bs(arr, left, middle - 1, value);        // #8
}

我們採用《複雜度分析實戰》中步伐分析的方式對 Code 1 的步伐進行分析. 我們記 \mathop {s}(n) 為 Code 1 的步伐. 其中, n 是陣列 arr 中的元素數量. if 陳述式 #1 的步伐是 1; return 陳述式 #2 和 #5 這兩個陳述式只會用到一個, 並且一次二分搜尋中只會用到一次, 因此這兩個陳述式的步伐總和為 1; 宣告陳述式 #3 的步伐為 1; if 陳述式 #4 和 #6 的步伐都是 1; return 陳述式 #7 和 #8 只會用到其中一個, 所以其步伐應該為 \mathop {s} \left ( \left \lfloor \frac {n}{2} \right \rfloor - 1 \right ) + 5 (因為各個函式引數的傳遞佔了 4 個步伐, 函式呼叫佔了 1 個步伐). 為了簡便起見, 那些常數步伐之和我們記為 c, 並且假設 n 總是偶數, 那麼我們有 \displaystyle {\mathop {s}(n) = \mathop {s} \left ( \frac {n}{2} - 1 \right ) + c}. 為了方便計算, 我們不執行 #7 或者 #8 的 +1 或者 -1 操作, 這樣雖然會拖慢演算法的效能產生重複的搜尋, 但是對複雜度計算不會發生量的影響, 於是有 \displaystyle {\mathop {s}(n) = \mathop {s} \left ( \frac {n}{2} \right ) + c}. 當陣列 arr 中沒有元素的時候, 函式 binary_search 不應該進行任何操作, 所以 \displaystyle {\mathop {s}(0) = 0}. 現在我們得到了遞迴方程式 \displaystyle {\mathop {s}(n) = \begin {cases} 0 & {n = 0} \\ \mathop {s} \left ( \frac {n}{2} \right ) + c & {n \geq 1}. \end {cases}} 我們僅考慮 n = 2^{k} 的情形, 對於 n \neq 2^{k} 的情形, 在漸近分析中我們可以通過適當擴大 n 的規模使得 n 滿足 n = 2^{k + 1}. 其中, k 為非負整數. 根據《遞迴方程式 —— 替代法與歸納法》, 當 n \geq 1 時, 有 \displaystyle {\begin {aligned} \mathop {s}(n) &= \mathop {s} \left ( \frac {n}{2} \right ) + c \\ &= \mathop {s} \left ( \frac {2^{k}}{2} \right ) + c \\ &= \mathop {s} \left ( 2^{k - 1} \right ) + c \\ &= \left ( \mathop {s} \left ( \frac {2^{k - 1}}{2} \right ) + c \right ) + c \\ &= \mathop {s} \left ( 2^{k - 2} \right ) + 2c \\ &= \left ( \mathop {s} \left ( \frac {2^{k - 3}}{2} \right ) + c \right ) + 2c \\ &= \mathop {s} \left ( 2^{k - 4} \right ) + 3c \\ &= ... \\ &= \mathop {s}(2) + (k - 1)c \\ &= kc. \end {aligned}} 由於 n = 2^{k}, 故有 k = \log_{2}{n}, 最終可得 \mathop {s}(n) = c \cdot \log_{2}{n}. 根據《漸近分析基礎》中大 Θ 記法的定義, 我們可得 \mathop {s}(n) = \Theta(\log {n}). 綜上所述, 二分搜尋法的時間複雜度為 \Theta(\log {n}).

3. 實作

int binary_search(const int arr[], int size, int value) {
    auto left {0}, right {size - 1};
    while(left <= right) {
        auto middle {(left + right) / 2};
        if(value == arr[middle]) {
            return middle;
        }else if(value < arr[middle]) {
            right = middle - 1;
        }else {
            left = middle - 1;
        }
    }
    return -1;
}

對於泛型版本的實作, 大家可以參考我的 GitHub : https://github.com/Jonny0201/data_structure/blob/master/data_structure/algorithm.hpp, 搜尋 binary_search 即可.