跳跃搜索

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 跳跃搜索算法
  2. 跳跃搜索示例
  3. 跳跃搜索算法的实现
  4. 跳跃搜索算法的复杂度
跳跃搜索

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

跳跃搜索算法

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

  • 从第一个元素开始设置 i0,块大小 m√n
  • A[min(m,n)-1]<Xi<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

  • i0m√93
  • A[2]X 小。设 i3m6
  • A[5]X 小。设 i6m9
  • A[8] 等于 X . 突破循环。
  • i 作为 6 小于 n
  • A[6] == 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),因为除了临时变量外,它不需要任何数据结构。

Harshit Jindal avatar Harshit Jindal avatar

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

相关文章 - Search Algorithm