算法——跳跃搜索

例如，假设我们有一个大小为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 <bits>
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] = n)
return -1;
}

// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] 
<p>输出：</p>
<p>Number 55 is at index 10</p>
<p>时间复杂度：O（√n）<br>
辅助空间：O（1）</p>
<p><strong>注意：</strong></p>
<p>该查找只针对已经排序的数组。<br>
要跳过的块的最佳大小是O（√n）。这使得跳跃搜索O（√n）的时间复杂度。<br>
跳跃搜索的时间复杂度在线性搜索（（O（n））和二进制搜索（O（Log n））之间。<br>
二进制搜索比跳跃搜索更好，但跳转搜索具有我们仅遍历一次的优点（二进制搜索可能需要最多为0（Log n）跳转），考虑要搜索的元素是最小元素或小于最小的）。因此，在跳回成本高昂的系统中，我们使用Jump Search。</p></bits>

登录后复制

以上就是算法——跳跃搜索的详细内容，更多请关注小闻网其它相关文章！