迹忆客 专注技术分享

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

1. 初始化 i 为 1。
2. A[1] = 2 < 10，所以将 i 递增到 2。
3. A[2] = 3 < 10，所以把 i 递增到 4。
4. A[4] = 5 < 10，所以把 i 递增到 8。
5. A[8] = 9 < 10，所以将 i 递增到 16。
6. i = 16 > n 因此在 i/2 范围内调用二叉搜索，即 8 到 min(i,n-1)，即 min(16,10) =10。
7. 初始化 lo 为 i/2 = 8，hi 为 min(i,n-1) = 10。
8. 计算 mid 为 9。
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)，因为除了临时变量外，它不需要任何额外的空间。