跳跃搜索算法

跳跃搜索算法是对线性搜索算法略微修改的版本。该算法的主要思想是通过比较比线性搜索算法更少的元素来减少时间复杂度。因此，输入数组被排序并分成块，以便在跳过这些块时执行搜索。

例如，让我们看看下面的例子；排序的输入数组在每个3个元素的块中进行搜索。所需的键仅在2次比较后找到，而不是线性搜索的6次比较。

这里出现了一个关于如何划分这些块的问题。为了回答这个问题，如果输入数组的大小为“n”，则块被划分为√n的区间。每个块的第一个元素都与键元素进行比较，直到键元素的值小于块元素。由于输入已排序，因此仅对之前的块执行线性搜索。如果找到元素，则表示搜索成功；否则，返回搜索失败。

本章将详细讨论跳跃搜索算法。

跳跃搜索算法

跳跃搜索算法将排序数组作为输入，该数组被分成较小的块以简化搜索。算法如下：

步骤1 - 如果输入数组的大小为“n”，则块的大小为√n。设置i = 0。

步骤2 - 将要搜索的键与数组的第i个元素进行比较。如果匹配，则返回元素的位置；否则，将i增加块大小。

步骤3 - 重复步骤2，直到第i个元素大于键元素。

步骤4 - 现在，由于输入数组已排序，因此可以确定元素位于前一个块中。因此，线性搜索应用于该块以查找元素。

步骤5 - 如果找到元素，则返回其位置。如果未找到元素，则提示搜索失败。

伪代码

Begin
   blockSize := √size
   start := 0
   end := blockSize
   while array[end] <= key AND end < size do
      start := end
      end := end + blockSize
      if end > size – 1 then
         end := size
   done
   for i := start to end -1 do
      if array[i] = key then
         return i
   done
   return invalid location
End

分析

跳跃搜索技术的时间复杂度为O(√n)，空间复杂度为O(1)。

示例

让我们通过从下面的排序数组A中搜索元素66来理解跳跃搜索算法：

步骤1

初始化 i = 0，输入数组大小 ‘n’ = 12

假设块大小表示为 ‘m’。那么，m = √n = √12 = 3

步骤2

将A[0]与键元素进行比较，并检查是否匹配，

A[0] = 0 ≠ 66

因此，i 增加块大小 3。现在与键元素比较的元素是 A[3]。

步骤3

A[3] = 14 ≠ 66

由于它不匹配，i 再次增加 3。

步骤4

A[6] = 48 ≠ 66

i 再次增加 3。将 A[9] 与键元素进行比较。

步骤5

A[9] = 88 ≠ 66

然而，88 大于 66，因此线性搜索应用于当前块。

步骤6

应用线性搜索后，指针从第6个索引增加到第7个。因此，将 A[7] 与键元素进行比较。

我们发现 A[7] 是所需元素，因此程序返回第7个索引作为输出。

实现

跳跃搜索算法是线性搜索的扩展变体。该算法将输入数组划分为多个较小的块，并在假设包含该元素的单个块上执行线性搜索。如果在假设的块中未找到该元素，则返回搜索失败。

输出打印数组中元素的位置而不是其索引。索引是指从 0 开始的数组索引号，而位置是存储元素的位置。

#include<stdio.h>
#include<math.h>
int jump_search(int[], int, int);
int main(){
   int i, n, key, index;
   int arr[12] = {0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126};
   int len = sizeof(arr)/sizeof(arr[0]);
   printf("Array elements are:");
   for(int j = 0; j<len; j++){
      printf(" %d", arr[j]);
   }
   n = 12;
   key = 66;
   printf("\nThe element to be searched: %d\n", key);
   index = jump_search(arr, n, key);
   if(index >= 0)
      printf("The element is found at position %d", index+1);
   else
      printf("Unsuccessful Search");
   return 0;
}
int jump_search(int arr[], int n, int key){
   int i, j, m, k;
   i = 0;
   m = sqrt(n);
   k = m;
   while(arr[m] <= key && m < n) {
      i = m;
      m += k;
      if(m > n - 1)
         return -1;
   }

   // linear search on the block
   for(j = i; j<m; j++) {
      if(arr[j] == key)
         return j;
   }
   return -1;
}

Array elements are: 0 6 12 14 19 22 48 66 79 88 104 126
The element to be searched: 66
The element is found at position 8

#include<iostream>
#include<cmath>
using namespace std;
int jump_search(int[], int, int);
int main(){
   int i, n, key, index;
   int arr[12] = {0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126};
   printf("Array elements are: ");
   for (auto j : arr){
      cout<<j<<" ";
   }
   n = 12;
   key = 66;
    cout<<"\nThe element to be searched: "<<key<<endl;
   index = jump_search(arr, n, key);
   if(index >= 0)
      cout << "The element is found at position " << index+1;
   else
      cout << "Unsuccessful Search";
   return 0;
}
int jump_search(int arr[], int n, int key){
   int i, j, m, k;
   i = 0;
   m = sqrt(n);
   k = m;
   while(arr[m] <= key && m < n) {
      i = m;
      m += k;
      if(m > n - 1)
         return -1;
   }

   // linear search on the block
   for(j = i; j<m; j++) {
      if(arr[j] == key)
         return j;
   }
   return -1;
}

Array elements are: 0 6 12 14 19 22 48 66 79 88 104 126 
The element to be searched: 66
The element is found at position 8

import java.io.*;
import java.util.Scanner;
import java.lang.Math;
public class JumpSearch {
   public static void main(String args[]) {
      int i, n, key, index;
      int arr[] = {0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126};
	  System.out.println("Array elements are: ");
	  for(int j = 0; j<arr.length; j++){
	     System.out.print(arr[j] + " ");
	  }
      n = 12;
      key = 66;
	  System.out.println("\nThe element to be searched: "+ key);
      index = jump_search(arr, n, key);
      if(index >= 0)
         System.out.print("The element is found at position " + (index+1));
      else
         System.out.print("Unsuccessful Search");
   }
   static int jump_search(int arr[], int n, int key) {
      int i, j, m, k;
      i = 0;
      m = (int)Math.sqrt(n);
      k = m;
      while(arr[m] <= key && m < n) {
         i = m;
         m += k;
         if(m > n - 1)
            return -1;
      }
      
      // linear search on the block
      for(j = i; j<m; j++) {
         if(arr[j] == key)
            return j;
      }
      return -1;
   }
}

Array elements are: 
0 6 12 14 19 22 48 66 79 88 104 126 
The element to be searched: 66
The element is found at position 8

import math
def jump_search(a, n, key):
   i = 0
   m = int(math.sqrt(n))
   k = m
   while(a[m] <= key and m < n):
      i = m
      m += k
      if(m > n - 1):
         return -1
   for j in range(m):
      if(arr[j] == key):
         return j
   return -1

arr = [0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126]
n = len(arr);
print("Array elements are: ")
for i in range(n):
   print(arr[i], end = " ")
key = 66
print("\nThe element to be searched: ", key)
index = jump_search(arr, n, key)
if(index >= 0):
   print("The element is found at position: ", (index+1))
else:
   print("\nUnsuccessful Search")

Array elements are: 
0 6 12 14 19 22 48 66 79 88 104 126 
The element to be searched:  66
The element is found at position:  8