设计与分析 - 跳转搜索

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

例如，让我们看看下面给出的例子；在每个包含 3 个元素的块中搜索已排序的输入数组。与线性搜索的 6 次比较相比，只有 2 次比较才能找到所需的键。

这里就出现了一个问题，如何划分这些块。为了回答这个问题，如果输入数组的大小为“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};
   n = 12;
   key = 66;
   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;
}

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};
   n = 12;
   key = 66;
   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;
}

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};
      n = 12;
      key = 66;
      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;
   }
}

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);
key = 66
index = jump_search(arr, n, key)
if(index >= 0):
   print("The element is found at position: ", (index+1))
else:
   print("Unsuccessful Search")

The element is found at position:  8