共计 1603 个字符，预计需要花费 5 分钟才能阅读完成。
| 导读 | 像二进制搜索一样，跳跃搜索是排序数组的搜索算法。基本思想是通过固定步骤跳过或跳过某些元素代替搜索所有元素来检查较少的元素（而不是线性搜索）。 |
例如，假设我们有一个大小为 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。
