指數搜尋
指數搜尋,也被稱為加倍搜尋或手指搜尋,是一種用於在大型陣列中搜尋元素而建立的演算法。它是一個兩步走的過程。首先,該演算法試圖找到目標元素存在的範圍 (L,R)
,然後在這個範圍內使用二叉搜尋來尋找目標的準確位置。
之所以命名為指數搜尋,是因為它通過搜尋索引 pow(2,k)
中哪個元素的第一個指數 k
大於目標元素,從而找到範圍內的持有元素。雖然它的名字叫指數搜尋,但這個演算法的時間複雜度是對數的。當陣列是無限大小時,它非常有用,而且收斂到解的速度比二叉搜尋快得多。
指數搜尋演算法
假設我們有一個未排序的陣列 A[]
,包含 n
個元素,我們想找到一個元素 X
。
-
檢查第一個元素本身是否是目標元素,即
A[0] == X
。 -
初始化
i
為1
。 -
當
i < n
且A[i] <= X
時,執行以下操作。- 將
i
以2
的冪數遞增,即i=i*2
。
- 將
-
在
i/2
到min(i,n-1)
的範圍內進行二叉搜尋。
指數搜尋示例
假設我們有一個陣列:(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
,我們想找到 X - 10
。
-
初始化
i
為1
。 -
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
範圍內呼叫二叉搜尋,即8
到min(i,n-1)
,即min(16,10) =10
。 -
初始化
lo
為i/2 = 8
,hi
為min(i,n-1) = 10
。 -
計算
mid
為9
。 -
10
=10
即A[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 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