Data Structures Algorithms 简明教程

Jump Search Algorithm

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

Jump Search algorithm is a slightly modified version of the linear search algorithm. The main idea behind this algorithm is to reduce the time complexity by comparing lesser elements than the linear search algorithm. The input array is hence sorted and divided into blocks to perform searching while jumping through these blocks.

例如，我们来看看以下给出的示例：对排序后的输入数组按每个 3 个元素的块进行搜索。所需键只在 2 次比较后找到，而不是线性搜索的 6 次比较。

For example, let us look at the given example below; the sorted input array is searched in the blocks of 3 elements each. The desired key is found only after 2 comparisons rather than the 6 comparisons of the linear search.

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

Here, there arises a question about how to divide these blocks. To answer that, if the input array is of size ‘n’, the blocks are divided in the intervals of √n. First element of every block is compared with the key element until the key element’s value is less than the block element. Linear search is performed only on that previous block since the input is sorted. If the element is found, it is a successful search; otherwise, an unsuccessful search is returned.

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

Jump search algorithm is discussed in detail further into this chapter.

Jump Search Algorithm

跳跃搜索算法将一个排序数组作为输入，将其划分成较小的块以使搜索变得更简单。算法如下−

The jump search algorithm takes a sorted array as an input which is divided into smaller blocks to make the search simpler. The algorithm is as follows −

*第 1 步 *−如果输入数组的大小为“n”，则块的大小为 √n。将 i = 0。

*Step 1 *− If the size of the input array is ‘n’, then the size of the block is √n. Set i = 0.

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

*Step 2 *− The key to be searched is compared with the ith element of the array. If it is a match, the position of the element is returned; otherwise i is incremented with the block size.

*第 3 步 *−重复第 2 步，直到第 i 个元素大于关键元素。

*Step 3 *− The Step 2 is repeated until the ith element is greater than the key element.

*第 4 步 *−现在，考虑到输入数组已排序，该元素被认为在先前的块中。因此，对该块应用线性搜索以找到该元素。

*Step 4 *− Now, the element is figured to be in the previous block, since the input array is sorted. Therefore, linear search is applied on that block to find the element.

*第 5 步 *−如果找到了该元素，则返回该位置。如果未找到该元素，则提示搜索失败。

*Step 5 *− If the element is found, the position is returned. If the element is not found, unsuccessful search is prompted.

Pseudocode

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

Analysis

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

The time complexity of the jump search technique is O(√n) and space complexity is O(1).

Example

让我们通过从给定的排序数组 A 中搜索元素 66 来理解跳跃搜索算法，如下所示 −

Let us understand the jump search algorithm by searching for element 66 from the given sorted array, A, below −

Step 1

初始化 i = 0，且输入数组“n”的大小 = 12

Initialize i = 0, and size of the input array ‘n’ = 12

假设将块大小表示为“m”。则，m = √n = √12 = 3

Suppose, block size is represented as ‘m’. Then, m = √n = √12 = 3

Step 2

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

Compare A[0] with the key element and check whether it matches,

A[0] = 0 ≠ 66

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

Therefore, i is incremented by the block size = 3. Now the element compared with the key element is A[3].

Step 3

A[3] = 14 ≠ 66

由于不是匹配项，i 再次以 3 递增。

Since it is not a match, i is again incremented by 3.

Step 4

A[6] = 48 ≠ 66

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

i is incremented by 3 again. A[9] is compared with the key element.

Step 5

A[9] = 88 ≠ 66

但是，88 大于 66，因此在当前块上应用线性搜索。

However, 88 is greater than 66, therefore linear search is applied on the current block.

Step 6

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

After applying linear search, the pointer increments from 6th index to 7th. Therefore, A[7] is compared with the key element.

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

We find that A[7] is the required element, hence the program returns 7th index as the output.

Implementation

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

The jump search algorithm is an extended variant of linear search. The algorithm divides the input array into multiple small blocks and performs the linear search on a single block that is assumed to contain the element. If the element is not found in the assumed blocked, it returns an unsuccessful search.

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

The output prints the position of the element in the array instead of its index. Indexing refers to the index numbers of the array that start from 0 while position is the place where the element is stored.