迹忆客 专注技术分享

跳跃搜索是一种区间搜索算法。它是一种相对较新的算法，只适用于排序数组。它试图比线性搜索减少所需的比较次数，不像线性搜索那样扫描每一个元素。在跳跃搜索中，数组被分成 m 块。它搜索一个块中的元素，如果该元素不存在，则移动到下一个块。当算法找到包含元素的块时，它使用线性搜索算法来寻找精确的索引。这种算法比线性搜索快，但比二叉搜索慢。

跳跃搜索算法

假设我们有一个未排序的数组 A[]，包含 n 个元素，我们想找到一个元素 X。

• 从第一个元素开始设置 i 为 0，块大小 m 为√n。
• 当 A[min(m,n)-1]<X 且 i<n 时。
  • 将 i 设为 m，并以√n 递增 m。
• If i >= n return -1。
• 当 A[i]< X 时，执行以下操作。
  • 递增 i
  • 如果 i 等于 min(m,n) 返回 -1。
• 如果 A[i] == X，返回 i。
• 否则，返回 -1。

跳跃搜索示例

假设我们有一个数组：(1, 2, 3, 4, 5, 6, 7, 8, 9)，我们想找到 X-7。

因为有 9 个元素，所以我们把 n 设为 9。

1. 设 i 为 0，m 为√9 即 3。
2. A[2] 比 X 小。设 i 为 3，m 为 6。
3. A[5] 比 X 小。设 i 为 6，m 为 9。
4. A[8] 等于 X . 突破循环。
5. i 作为 6 小于 n。
6. A[6] == 7，跳出循环。
7. 因为 A[6]=7，所以返回 6。

跳跃搜索算法的实现

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

int jumpSearch(int arr[], int x, int n)
{

    int m = sqrt(n);
    int i = 0;
    while (arr[min(m, n) - 1] < x)
    {
        i = m;
        m += sqrt(n);
        if (i >= n)
            return -1;
    }
    while (arr[i] < x)
    {
        i++;
        if (i == min(m, n))
            return -1;
    }
    if (arr[i] == x)
        return i;

    return -1;
}

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

跳跃搜索算法的复杂度

时间复杂度

• 平均情况

跳跃排序算法运行 n/m 次，其中 n 是元素数量，m 是块大小。线性搜索需要 m-1 次比较，使得总时间表达式为 n/m+m-1。使时间表达式最小化的 m 的最优值为√n，使得时间复杂度为 n/√n+√n，即√n。跳跃搜索算法的时间复杂度为 O(√n)。

• 最佳情况

最佳情况下的时间复杂度是 O(1)。当要搜索的元素是数组中的第一个元素时，就会出现这种情况。

• 最坏情况

最坏的情况发生在我们做 n/m 跳跃的时候，我们最后检查的值大于我们要搜索的元素，m-1 比较进行线性搜索。最坏情况下的时间复杂度为 O(√n)。

空间复杂度

这种算法的空间复杂度是 O(1)，因为除了临时变量外，它不需要任何数据结构。