Data Structures Algorithms 简明教程

Jump Search Algorithm

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

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

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

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

Jump Search Algorithm

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

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

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

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

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

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

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