# 算法设计：跳转搜索算法原理解析和实现

2021年4月15日17:16:58 发表评论 1,050 次浏览

## 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 math

def 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 prev

return - 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#

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

function 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``

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

https://en.wikipedia.org/wiki/Jump_search