良许Linux教程网 干货合集 详解跳跃搜索算法

详解跳跃搜索算法

Jump Search 跳跃搜索算法跟二分查找算法类似,它也是针对有序序列的查找,只是它是通过查找比较少的元素找到目标。当然它需要通过固定的跳跃间隔,这样它相比二分查找效率提高了很多。

img

例如,假设我们有一个大小为n的数组arr []和块(要跳转)的大小m。然后我们搜索索引arr [0],arr [m],arr [2m] … ..arr [km]等等。一旦我们找到间隔(arr [km]

我们考虑以下数组:(0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610)。数组的长度为16.跳跃搜索将以下列步骤找到55,假设要跳过的块大小为4.

步骤1:从索引0跳转到索引4; 步骤2:从索引4跳转到索引8; 步骤3:从索引8跳转到索引16; 步骤4:由于索引16处的元素大于55,因此我们将返回一步到索引9. 步骤5:从索引9执行线性搜索以获取元素55。

要跳过的最佳块大小是多少?

在最坏的情况下,我们必须进行n / m跳转,如果最后一个检查值大于要搜索的元素,则对线性搜索进行m-1比较。因此,最坏情况下的比较总数将为((n / m)+ m-1)。当m =√n时,函数((n / m)+ m-1)的值将是最小值。因此,最好的步长是m = √n。

// C++ program to implement Jump Search

#include 
using namespace std;

int jumpSearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt(n);

// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] if (prev >= n)
return -1;
}

// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] if (prev == min(step, n))
return -1;
}
// If element is found
if (arr[prev] == x)
return prev;

return -1;
}

// Driver program to test function
int main()
{
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610 };
int x = 55;
int n = sizeof(arr) / sizeof(arr[0]);

// Find the index of 'x' using Jump Search
int index = jumpSearch(arr, x, n);

// Print the index where 'x' is located
cout "\nNumber " " is at index " return 0;
}

// Contributed by nuclode

输出:

Number 55 is at index 10

时间复杂度:O(√n) 辅助空间:O(1)

注意:

该查找只针对已经排序的数组。 要跳过的块的最佳大小是O(√n)。这使得跳跃搜索O(√n)的时间复杂度。 跳跃搜索的时间复杂度在线性搜索((O(n))和二进制搜索(O(Log n))之间。 二进制搜索比跳跃搜索更好,但跳转搜索具有我们仅遍历一次的优点(二进制搜索可能需要最多为0(Log n)跳转),考虑要搜索的元素是最小元素或小于最小的)。因此,在跳回成本高昂的系统中,我们使用Jump Search。

以上就是良许教程网为各位朋友分享的Linu系统相关内容。想要了解更多Linux相关知识记得关注公众号“良许Linux”,或扫描下方二维码进行关注,更多干货等着你 !

img
本文由 良许Linux教程网 发布,可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。
良许

作者: 良许

良许,世界500强企业Linux开发工程师,公众号【良许Linux】的作者,全网拥有超30W粉丝。个人标签:创业者,CSDN学院讲师,副业达人,流量玩家,摄影爱好者。
上一篇
下一篇

发表评论

邮箱地址不会被公开。 必填项已用*标注

联系我们

联系我们

公众号:良许Linux

在线咨询: QQ交谈

邮箱: yychuyu@163.com

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部