跳跃搜索算法
跳跃搜索算法是线性搜索算法的一个略微修改的版本。该算法的主要思想是通过比较比线性搜索算法更少的元素来降低时间复杂度。因此，输入数组被排序并分成多个块，以便在这些块之间跳跃搜索。
例如，让我们看下面的例子；对排序后的输入数组进行搜索，每个块包含 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("
The element to be searched: %d
", 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;
}
// 在块上进行线性搜索
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<<"
The 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;
}
// 在块上进行线性搜索
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("
The 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;
}
// 在块上进行线性搜索
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("
The 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("
Unsuccessful 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
