迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 算法 >

跳跃搜索

作者:迹忆客 最近更新:2023/03/20 浏览次数:

跳跃搜索是一种区间搜索算法。它是一种相对较新的算法,只适用于排序数组。它试图比线性搜索减少所需的比较次数,不像线性搜索那样扫描每一个元素。在跳跃搜索中,数组被分成 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),因为除了临时变量外,它不需要任何数据结构。

上一篇:斐波那契搜索

下一篇:指数搜索

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

将二叉树转换为二叉搜索树

发布时间:2023/03/20 浏览次数:159 分类:算法

本教程教大家如何将二叉树转换为二叉搜索树。二叉树是一种非线性数据结构。它被称为二叉树,因为每个节点最多有两个子节点。这些子节点被称为左子和右子。

二叉搜索树删除

发布时间:2023/03/20 浏览次数:164 分类:算法

本教程介绍了二叉搜索树的删除操作。

二叉搜索树检查

发布时间:2023/03/20 浏览次数:151 分类:算法

如何检查给定的二叉树是否是二叉搜索树。

二叉搜索树

发布时间:2023/03/20 浏览次数:105 分类:算法

本教程介绍了数据结构 Binary Search Tree。

二叉树遍历

发布时间:2023/03/20 浏览次数:202 分类:算法

本教程介绍了二叉树上的树遍历中序遍历、前序遍历和后序遍历。

循环双向链表

发布时间:2023/03/20 浏览次数:143 分类:算法

本教程介绍了循环双向链表的数据结构。

循环链接列表

发布时间:2023/03/20 浏览次数:188 分类:算法

本教程介绍了循环链接列表的数据结构。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便