算法——跳跃搜索

分手后的思念是犯贱 2022-06-04 04:53 220阅读 0赞

**像二进制搜索一样，跳跃搜索是排序数组的搜索算法。基本思想是通过固定步骤跳过或跳过某些元素代替搜索所有元素来检查较少的元素（而不是线性搜索）。**

例如，假设我们有一个大小为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。