指数搜索
指数搜索,也被称为加倍搜索或手指搜索,是一种用于在大型数组中搜索元素而创建的算法。它是一个两步走的过程。首先,该算法试图找到目标元素存在的范围 (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