指數搜尋 Exponential Search

指數搜尋,又稱為 galloping search,是一種特殊的二元搜尋,主要用在搜尋無限、無邊界的已排序序列。由於邊界未知長度就未知,無法以傳統二元搜尋來找中點。而 Exponential 顧名思義就是從底數為 2,指數為 0 的索引($2^0$ )開始,不斷比較在 $2^1$、$2^2$ 直到 $2^k$ 位置上的值,若比目標值大,則停止指數成長,直接從該位置執行二元搜尋,回頭尋找目標值。

指數搜尋的特點如下:

  • 可以搜尋邊界未知的已排序序列。
  • 縮小搜尋範圍,可比 naïve 的二元搜尋效率高些。
  • 若目標值實際位置很靠近序列前端,效率會非常棒。

步驟

指數搜尋的步驟只有非常簡單的兩步驟:

  1. 依照目標值大小,劃出搜尋範圍。
  2. 在上述範圍內執行二元搜尋。

而劃出搜尋範圍這部分也很直觀:

  1. 選定一個底數 $k$,通常為 2。
  2. 比較 $k^i$ 索引下的值是否比目標值大,$i$ 從零開始。
  3. 若較小,指數加一 $k^{i + 1}$ 後繼續重複步驟二比較。
  4. 若較大,停止比較,得搜尋範圍為 $k^{i - 1}$ 到 $k^i$。

說明

這裡有個排好序的序列,我們要尋找其中是否有 22 這個數字。

    *
[2, 3, 3, 6, 6, 7, 9, 13, 15, 19, 20, 22, 23, 24, 25]

首先,先尋找 $2^0 = 1$ 位置上的數字是否超過 22。3 < 22,很明顯沒有。

       *     *            *
[2, 3, 3, 6, 6, 7, 9, 13, 15, 19, 20, 22, 23, 24, 25]

再來,連續看看

  • $2^1$:3 < 22
  • $2^2$:6 < 22
  • $2^3$:15 < 22

也都沒有超越 22。

                                                           *
[2, 3, 3, 6, 6, 7, 9, 13, 15, 19, 20, 22, 23, 24, 25]  _,  _

最後,一口氣將指數加到 4,看看$2^4$ 上的數字是否大於 22。哎呀,$2^4 = 16$,的位置已經超出序列長度,因此取至序列最後一個數字作為比較對象。25 > 22,找到了!

得到搜尋的範圍是 $$2^{4-1} < x < \text{array.length} < 2^{4}$$

效能

Complexity
Worst $O(\log i)$
Best $O(1)$
Average $O(\log i)$
Worst space $O(1)$

$i$:目標值在序列中實際的索引位置。

指數搜尋的複雜度分為兩部分分析:

劃定搜尋範圍

設 $i$ 為目標值在序列中實際的索引位置,則搜尋上界,指數增加的操作需執行 $\lceil \log(i) \rceil$ 次,例如匹配目標值的搜尋結果位於序列第 9 個,則指數需增加 $\lceil \log(9) \rceil = 4$ 次,上界才會超過目標值。我們設這部分的複雜度為 $O(log i)$。

執行二元搜尋

第二部分就是二元搜尋,複雜度為 $O(log n)$,$n$ 為搜尋範圍的長度。根據第一部分,可以得知範圍長度為 $2^{\log i} - 2^{\log{i - 1}} = 2^{log{i - 1}}$ 個元素,帶入二元搜尋的複雜度,計算出第二部分的複雜度為 $log (2^{\log{i - 1}}) = \log{(i)} - 1 = O(\log i)$。

最後,將兩部分的複雜度合起來,就是指數搜尋的時間複雜度了。

$$O(\log i) + O(\log i) = 2 O(\log i) = O(\log i)$$

實作

本次實作有邊界的指數搜尋,主要分為三個部分:

  1. 處理空序列的狀況。
  2. 利用指數,決定搜尋範圍。
  3. 執行二元搜尋,並將輸出結果映射回原始序列。

話不多說,直接看程式碼。


# #![allow(unused_variables)]
#fn main() {
use crate::searching::binary_search;

pub fn exponential_search<T>(arr: &[T], target: &T) -> Result<usize, usize>
    where T: PartialOrd
{
    // 1. Handle empty scenario.
    let size = arr.len();
    if size == 0 {
        return Err(0);
    }

    // 2. Determine searching boundaries.
    let mut hi = 1_usize; // Upper bound.
    while hi < size && arr[hi] < *target {
        hi <<= 1;
    }
    let lo = hi >> 1; // Lower bound.

    // 3. Do binary search.
    binary_search(&arr[lo..size.min(hi + 1)], target)
        .map(|index| lo + index)
        .map_err(|index| lo + index)
}
#}
  1. 和二元搜尋同,遇到空序列就返回 Err(0) 告知呼叫端可新增資料在位置 0。
  2. 決定搜尋上下界,只要 上界不超過序列長度,且 arr[hi] 小於目標值,就讓上界指數成長。這裡用位元左移運算子(bitwise left shift)實作乘以 2。
    找到上界後,再將上界除以 2(位元右移),就是下界了。
  3. 確定範圍後,利用上下界切序列的 sub slice 作為引數,傳遞給二元搜尋。要注意的是,為了避免 sub slice 超出邊界,上界需在 sizehi + 1 之間找最小值。
    由於回傳結果的位置是以 sub slice 起始,需加上位移量(下界 lo)才會對應原始 slice 的位置。

由於內部使用二元搜尋,若該二元搜尋沒有處理重複元素的狀況,指數搜尋連帶無法預期這個行為。

參考資料

Wiki: Exponential search