Data Structures Algorithms 简明教程

Exponential Search Algorithm

指数级搜索算法针对输入数组的一个范围，它假定所需元素必须存在于该范围中，并在该特定小范围内执行二分搜索。此算法也称为加倍搜索或手指搜索。

它类似于跳跃搜索，将已排序的输入分成多个块，并进行小规模搜索。然而，在对块进行划分来执行计算和应用的小规模搜索类型（跳跃搜索应用线性搜索和指数搜索应用二分搜索）时会出现差异。

因此，这种算法以指数方式跳过 2 的各个幂。用更简单的语言来说，对使用 pow(2, k) 划分的块执行搜索，其中 k 是大于或等于 0 的整数。一旦位于 pow(2, n) 位置的元素大于关键字元素，便对当前块执行二分搜索。

Exponential Search Algorithm

在指数搜索算法中，跳跃从数组的第 1 个索引开始。因此，我们在算法的第一步手动比较第一个元素。

步骤 1 − 将数组中的第一个元素与关键字进行比较，如果找到匹配项，则返回第 0 个索引。

步骤 2 − 初始化 i = 1，并将数组的第 i 个元素与要搜索的关键字进行比较。如果匹配，则返回该索引。

步骤 3 − 如果元素不匹配，则在 2 的各个幂中按指数跳过该数组。因此，现在算法比较位于增量位置的元素。

步骤 4 − 如果找到匹配项，则返回该索引。否则，重复步骤 2，直到位于增量位置的元素大于要搜索的关键字为止。

步骤 5 − 由于下一个增量比关键字的元素高并且输入已排序，因此算法对当前块应用二分搜索算法。

步骤 6 − 如果找到匹配项，则返回关键字所在的索引；否则，确定为未成功搜索。

Pseudocode

Begin
   m := pow(2, k) // m is the block size
   start := 1
   low := 0
   high := size – 1 // size is the size of input
   if array[0] == key
      return 0
   while array[m] <= key AND m < size do
      start := start + 1
      m := pow(2, start)
      while low <= high do:
         mid = low + (high - low) / 2
         if array[mid] == x
            return mid
         if array[mid] < x
            low = mid + 1
         else
            high = mid - 1
   done
   return invalid location
End