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

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

本文概述

像二元搜寻, 跳转搜索是一种用于排序数组的搜索算法。基本思想是检查更少的元素(比线性搜索), 以固定的步骤向前移动或跳过某些元素来代替搜索所有元素。

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

时间复杂度：O(√n)

辅助空间：O(1)

要点：

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

参考文献：

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

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: