介绍

指数搜索用于通过跳跃指数位置（即 2 的幂）来搜索元素。试图找到一个相对较小的范围，在该范围内可使用其他有界搜索算法（例如二进制搜索）来搜索元素。

原理

试图找到一个比搜索的元素更大的元素，目的是为了最大程度地减少所需元素的范围。通过将其乘以 2 来增加范围，然后再次检查是否到达的元素大于要搜索的元素或数组的末尾。一旦达到这两个目的，便会跳出循环。然后，使用 startIndex range/2 和 lastIndex 执行二进制搜索 range。

复杂度

• 平均时间复杂度：${\displaystyle O(\log i)}$
• 最坏时间复杂度：${\displaystyle O(\log i)}$
• 最优时间复杂度：${\displaystyle O(1)}$
• 空间复杂度：迭代：${\displaystyle O(1)}$

实现

JavaScript

/**
 * Exponential Search
 *
 * The algorithm consists of two stages. The first stage determines a
 * range in which the search key would reside if it were in the list.
 * In the second stage, a binary search is performed on this range.
 */

function binarySearch (arr, value, floor, ceiling) {
  // Middle index
  const mid = Math.floor((floor + ceiling) / 2)

  // If value is at the mid position return this position
  if (arr[mid] === value) {
    return mid
  }

  if (floor > ceiling) return -1

  // If the middle element is great than the value
  // search the left part of the array
  if (arr[mid] > value) {
    return binarySearch(arr, value, floor, mid - 1)
    // If the middle element is lower than the value
    // search the right part of the array
  } else {
    return binarySearch(arr, value, mid + 1, ceiling)
  }
}

function exponentialSearch (arr, length, value) {
  // If value is the first element of the array return this position
  if (arr[0] === value) {
    return 0
  }

  // Find range for binary search
  let i = 1
  while (i < length && arr[i] <= value) {
    i = i * 2
  }

  // Call binary search for the range found above
  return binarySearch(arr, value, i / 2, Math.min(i, length))
}

参考

• Exponential search - Wikipedia (opens new window)