算法——跳跃搜索

例如，假设我们有一个大小为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/stdc++.h>
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] < x) { prev = step; step += sqrt(n); if (prev >= n)
return -1;
}

// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] < x)
{
prev++;

// If we reached next block or end of
// array, element is not present.
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 " << x << " is at index " << 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。