指數搜尋

1. 指數搜尋演算法
2. 指數搜尋示例
3. 指數搜尋演算法的實現
4. 指數搜尋演算法的複雜度

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

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

指數搜尋演算法

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

指數搜尋示例

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

指數搜尋演算法的實現

#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)，因為除了臨時變數外，它不需要任何額外的空間。