算法设计（跳转搜索算法原理解析和实现）

本文概述

C++
Java
Python3
C#
PHP

像二元搜寻, 跳转搜索是一种用于排序数组的搜索算法。基本思想是检查更少的元素(比线性搜索), 以固定的步骤向前移动或跳过某些元素来代替搜索所有元素。
例如, 假设我们有一个大小为n的数组arr[]和块(要跳转)大小为m。然后, 我们在索引arr[0], arr[m], arr[2m] ..... arr[km]等处进行搜索。一旦找到间隔(arr[km] < x < arr[(k + 1)m]), 我们将从索引km执行线性搜索操作以找到元素x。
让我们考虑以下数组：(0、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610)。数组的长度为16。假设要跳转的块大小为4, 跳转搜索将通过以下步骤找到值55。
步骤1：从索引0跳到索引4；
步骤2：从索引4跳至索引8；
步骤3：从索引8跳到索引12；
第4步：由于索引12处的元素大于55, 因此我们将后退一步以进入索引8。
步骤5：从索引8执行线性搜索以获取元素55。
要跳过的最佳块大小是多少？
在最坏的情况下, 我们必须执行n/m次跳转, 如果最后一次检查的值大于要搜索的元素, 则对于线性搜索, 我们将执行m-1个比较。因此, 最坏情况下的比较总数为((n/m)+ m-1)。当m =√n时, 函数的值((n/m)+ m-1)最小。因此, 最佳步长为m =√n。
C++

//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

Java

//Java program to implement Jump Search. public class JumpSearch { public static int jumpSearch( int [] arr, int x) { int n = arr.length; //Finding block size to be jumped int step = ( int )Math.floor(Math.sqrt(n)); //Finding the block where element is //present (if it is present) int prev = 0 ; while (arr[Math.min(step, n)- 1 ] < x) { prev = step; step += ( int )Math.floor(Math.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 == Math.min(step, n)) return - 1 ; }//If element is found if (arr[prev] == x) return prev; return - 1 ; }//Driver program to test function public static void main(String [ ] args) { int arr[] = { 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 }; int x = 55 ; //Find the index of 'x' using Jump Search int index = jumpSearch(arr, x); //Print the index where 'x' is located System.out.println( "\nNumber " + x + " is at index " + index); } }

Python3

# Python3 code to implement Jump Search import mathdef jumpSearch( arr , x , n ):# Finding block size to be jumped step = math.sqrt(n)# Finding the block where element is # present (if it is present) prev = 0 while arr[ int ( min (step, n) - 1 )] < x: prev = step step + = math.sqrt(n) if prev> = n: return - 1# Doing a linear search for x in # block beginning with prev. while arr[ int (prev)] < x: prev + = 1# 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[ int (prev)] = = x: return prevreturn - 1# Driver code to test function arr = [ 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , 377 , 610 ] x = 55 n = len (arr)# Find the index of 'x' using Jump Search index = jumpSearch(arr, x, n)# Print the index where 'x' is located print ( "Number" , x, "is at index" , "%.0f" % index)# This code is contributed by "Sharad_Bhardwaj".

//C# program to implement Jump Search. using System; public class JumpSearch { public static int jumpSearch( int [] arr, int x) { int n = arr.Length; //Finding block size to be jumped int step = ( int )Math.Floor(Math.Sqrt(n)); //Finding the block where element is //present (if it is present) int prev = 0; while (arr[Math.Min(step, n)-1] < x) { prev = step; step += ( int )Math.Floor(Math.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 == Math.Min(step, n)) return -1; }//If element is found if (arr[prev] == x) return prev; return -1; }//Driver program to test function public static void Main() { int [] arr = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}; int x = 55; //Find the index of 'x' using Jump Search int index = jumpSearch(arr, x); //Print the index where 'x' is located Console.Write( "Number " + x + " is at index " + index); } }

PHP

< ?php //PHP program to implement Jump Searchfunction jumpSearch( $arr , $x , $n ) { //Finding block size to be jumped $step = sqrt( $n ); //Finding the block where element is //present (if it is present) $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 $arr = array ( 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 ); $x = 55; $n = sizeof( $arr ) /sizeof( $arr[0]); //Find the index of '$x' using Jump Search $index = jumpSearch( $arr , $x , $n ); //Print the index where '$x' is located echo "Number " . $x . " is at index " . $index ; return 0; ?>

输出如下：

Number 55 is at index 10

【算法设计（跳转搜索算法原理解析和实现）】时间复杂度：O(√n)
辅助空间：O(1)
要点：

仅适用于排序数组。
要跳转的块的最佳大小为(√n)。这使得跳转搜索的时间复杂度为O(√n)。
跳转搜索的时间复杂度介于线性搜索((O(n))和二进制搜索(O(Log n))之间。
二进制搜索比跳转搜索要好, 但是跳转搜索的优势是我们仅回溯一次(二进制搜索可能需要最多O(Log n)个跳转, 请考虑以下情况：要搜索的元素是最小元素或小于元素最小的)。因此, 在二进制搜索成本很高的系统中, 我们使用跳转搜索。

参考文献：
https://en.wikipedia.org/wiki/Jump_search