指數搜尋

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 指數搜尋演算法
  2. 指數搜尋示例
  3. 指數搜尋演算法的實現
  4. 指數搜尋演算法的複雜度
指數搜尋
注意
如果你不知道什麼是二叉搜尋,那麼首先請你在這裡看一下二叉搜尋演算法

指數搜尋,也被稱為加倍搜尋或手指搜尋,是一種用於在大型陣列中搜尋元素而建立的演算法。它是一個兩步走的過程。首先,該演算法試圖找到目標元素存在的範圍 (L,R),然後在這個範圍內使用二叉搜尋來尋找目標的準確位置。

之所以命名為指數搜尋,是因為它通過搜尋索引 pow(2,k) 中哪個元素的第一個指數 k 大於目標元素,從而找到範圍內的持有元素。雖然它的名字叫指數搜尋,但這個演算法的時間複雜度是對數的。當陣列是無限大小時,它非常有用,而且收斂到解的速度比二叉搜尋快得多。

指數搜尋演算法

假設我們有一個未排序的陣列 A[],包含 n 個元素,我們想找到一個元素 X

  • 檢查第一個元素本身是否是目標元素,即 A[0] == X
  • 初始化 i1
  • i < nA[i] <= X 時,執行以下操作。
    • i2 的冪數遞增,即 i=i*2
  • i/2min(i,n-1) 的範圍內進行二叉搜尋。

指數搜尋示例

假設我們有一個陣列:(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11),我們想找到 X - 10

  • 初始化 i1
  • A[1] = 2 < 10,所以將 i 遞增到 2
  • A[2] = 3 < 10,所以把 i 遞增到 4
  • A[4] = 5 < 10,所以把 i 遞增到 8
  • A[8] = 9 < 10,所以將 i 遞增到 16
  • i = 16 > n 因此在 i/2 範圍內呼叫二叉搜尋,即 8min(i,n-1),即 min(16,10) =10
  • 初始化 loi/2 = 8himin(i,n-1) = 10
  • 計算 mid9
  • 10=10A[9] == X,因此返回 9

指數搜尋演算法的實現

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int lo, int hi, int x)
{
    while (lo <= hi) {
        int m = lo + (hi - lo) / 2;
        if (arr[m] == x)
            return m;
        if (arr[m] < x)
            lo = m + 1;
        else
            hi = m - 1;
    }
    return -1;
}

int exponentialSearch(int arr[], int n, int x)
{
    if (arr[0] == x)
        return 0;
    int i = 1;
    while (i < n && arr[i] <= x)
        i = i * 2;

    return binarySearch(arr, i / 2,
                        min(i, n - 1), x);
}

int main()
{
    int n = 11;
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
    int x = 10;
    int result = exponentialSearch(arr, n, x);
    if (result == -1) {
        cout << "Element not found !!";
    }
    else cout << "Element found at index " << result;
    return 0;
}

指數搜尋演算法的複雜度

時間複雜度

  • 平均情況

平均情況下的時間複雜度為 O(logi),其中 i 是陣列內目標元素 X 的索引。當元素接近陣列的開始時,它甚至優於二叉搜尋。

  • 最佳情況

當我們比較的元素是我們正在搜尋的元素,並且在第一次迭代中被返回時,就會出現最佳情況。最佳情況下的時間複雜度是 O(1)

  • 最壞情況

最壞情況下的時間複雜度與平均情況下的時間複雜度相同。最壞情況下的時間複雜度是 O(logi)

空間複雜度

這種演算法的空間複雜度是 O(1),因為除了臨時變數外,它不需要任何額外的空間。

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Search Algorithm