Data Structures Algorithms 简明教程

Exponential Search Algorithm

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

Exponential search algorithm targets a range of an input array in which it assumes that the required element must be present in and performs a binary search on that particular small range. This algorithm is also known as doubling search or finger search.

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

It is similar to jump search in dividing the sorted input into multiple blocks and conducting a smaller scale search. However, the difference occurs while performing computations to divide the blocks and the type of smaller scale search applied (jump search applies linear search and exponential search applies binary search).

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

Hence, this algorithm jumps exponentially in the powers of 2. In simpler words, the search is performed on the blocks divided using pow(2, k) where k is an integer greater than or equal to 0. Once the element at position pow(2, n) is greater than the key element, binary search is performed on the current block.

Exponential Search Algorithm

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

In the exponential search algorithm, the jump starts from the 1st index of the array. So we manually compare the first element as the first step in the algorithm.

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

*Step 1 *− Compare the first element in the array with the key, if a match is found return the 0th index.

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

*Step 2 *− Initialize i = 1 and compare the ith element of the array with the key to be search. If it matches return the index.

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

*Step 3 *− If the element does not match, jump through the array exponentially in the powers of 2. Therefore, now the algorithm compares the element present in the incremental position.

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

*Step 4 *− If the match is found, the index is returned. Otherwise Step 2 is repeated iteratively until the element at the incremental position becomes greater than the key to be searched.

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

*Step 5 *− Since the next increment has the higher element than the key and the input is sorted, the algorithm applies binary search algorithm on the current block.

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

*Step 6 *− The index at which the key is present is returned if the match is found; otherwise it is determined as an unsuccessful search.

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

Analysis

即使它被称为指数搜索，它也不会以指数时间复杂度执行搜索。但是，正如我们所知，在此搜索算法中，执行的基本搜索是二分搜索。因此，指数搜索算法的时间复杂度与二分搜索算法的时间复杂度相同， O(log n) 。

Even though it is called Exponential search it does not perform searching in exponential time complexity. But as we know, in this search algorithm, the basic search being performed is binary search. Therefore, the time complexity of the exponential search algorithm will be the same as the binary search algorithm’s, O(log n).

Example

为了更好地、更简单地理解指数搜索算法，让我们使用指数搜索算法在示例输入数组中搜索元素−

To understand the exponential search algorithm better and in a simpler way, let us search for an element in an example input array using the exponential search algorithm −

提供给搜索算法的排序输入数组如下−

The sorted input array given to the search algorithm is −

让我们在给定的数组中搜索元素 81 的位置。

Let us search for the position of element 81 in the given array.

Step 1

将数组的第一个元素与关键字元素 81 进行比较。

Compare the first element of the array with the key element 81.

数组的第一个元素是 6，但要搜索的关键字元素是 81；因此，由于没有找到匹配项，此跳跃从第 1 个索引开始。

The first element of the array is 6, but the key element to be searched is 81; hence, the jump starts from the 1st index as there is no match found.

Step 2

在初始化 i = 1 之后，将关键字元素与第一个索引中的元素进行比较。此处，第 1 个索引中的元素与关键字元素不匹配。因此，它再次以指数方式按 2 的幂进行递增。

After initializing i = 1, the key element is compared with the element in the first index. Here, the element in the 1st index does not match with the key element. So it is again incremented exponentially in the powers of 2.

索引增加到 2m = 21 = 将第 2 个索引中的元素与关键字元素进行比较。

The index is incremented to 2m = 21 = the element in 2nd index is compared with the key element.

仍然不匹配，因此再次进行递增。

It is still not a match so it is once again incremented.

Step 3

索引再次以指数方式按 2 的幂递增。

The index is incremented in the powers of 2 again.

22 = 4 = 将第 4 个索引中的元素与关键元素进行比较，但尚未找到匹配项。

22 = 4 = the element in 4th index is compared with the key element and a match is not found yet.

Step 4

索引再次成倍增加。这一次，将第 8 个索引中的元素与关键元素进行比较，但尚未找到匹配项。

The index is incremented exponentially once again. This time the element in the 8th index is compared with the key element and a match is not found.

但是，第 8 个索引中的元素大于关键元素。因此，将二分搜索算法应用于当前元素块。

However, the element in the 8th index is greater than the key element. Hence, the binary search algorithm is applied on the current block of elements.

Step 5

当前元素块包括索引 [4, 5, 6, 7] 中的元素。

The current block of elements includes the elements in the indices [4, 5, 6, 7].

在这个元素块上应用小规模二分搜索，其中计算中值为第 5 个元素。

Small scale binary search is applied on this block of elements, where the mid is calculated to be the 5th element.

Step 6

在中值元素处未找到匹配项，并得出期望的元素大于中值元素的结论。因此，搜索发生在块的右半部分。

The match is not found at the mid element and figures that the desired element is greater than the mid element. Hence, the search takes place is the right half of the block.

现在，中值设置为第 6 个元素 -

The mid now is set as 6th element −

Step 7

元素仍未在第 6 个元素中找到，因此现在在中值元素的右半部分进行搜索。

The element is still not found at the 6th element so it now searches in the right half of the mid element.

下一个中值设置为第 7 个元素。

The next mid is set as 7th element.

在这里，在第 7 个索引处找到了元素。

Here, the element is found at the 7th index.

Implementation

在指数搜索算法的实现中，程序检查以 2 的幂为单位的每个指数跳跃处的匹配项。如果找到匹配项，则返回元素的位置，否则程序返回搜索不成功。

In the implementation of the exponential search algorithm, the program checks for the matches at every exponential jump in the powers of 2. If the match is found the location of the element is returned otherwise the program returns an unsuccessful search.

一旦某个指数跳跃处的元素大于关键元素，便在当前元素块上执行二分搜索。

Once the element at an exponential jump becomes greater than the key element, a binary search is performed on the current block of elements.

在本章中，我们将研究使用四种不同语言实现指数搜索。

In this chapter, we will look into the implementation of exponential search in four different languages.