指数搜索(Exponential Search)算法又称为双倍搜索(Doubling Search)算法或是蔓延搜索(Galloping Search)算法,是二元搜索(Binary Search)算法的变体。这套算法可以在已排序好的串行中进行高效率的搜索,要搜索的元素在串行中愈前面的话,搜索性能愈好。
指数搜索法(Exponential Search)
指数搜索法的概念
指数搜索法是基于二元搜索法的算法,如果您还不了解二元搜索法的话,请先参考这篇文章:
指数搜索法与二元搜索法的差异在于,它在一开始的时候,并不是直接去选择串行中间的元素来比较,而是先去比较索引值为 20 = 1 的元素。如果发现要查找的元素比索引值为 20 的元素还要小,表示要查找的元素不是在索引值 0 的位置上,要不然就是不在串行中;如果要查找的元素比索引值为 20 的元素还要大,表示要查找的元素可能会出现在索引值为 20 之后,此时再继续比较要查找的元素与索引值为 20 + i = 2i 的元素,i 为 1, 2, 3, ...。如果在 i 迭代的过程中发现该索引值对应的元素比要查找的元素还要大时,就可以用二元搜索法来搜索索引值 2i - 1 + 1 ~ 2i - 1 的范围中,是否有我们要查找的元素;如果串行是有限的,且在 i 迭代的过程中找不到比要查找的元素还要大的元素,则可以直接用二元搜索法来搜索索引值 2i - 1 + 1 ~ 串行长度 - 1 的范围。
指数搜索法的过程
假设现在有个已排序好的整数数组,内容如下:
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
然后我们要用指数搜索法来找到元素 47。一开始先比较索引值为 20 = 1 的元素和要查找的元素 47 的大小。
●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
47 > 9
由于查找的元素 47 比索引值为 20 = 1 的元素 9 还要大,因此继续与索引值为 2i + 1 = 20 + 1 = 21 = 2 的元素做比较。
●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
47 > 30
由于查找的元素 47 比索引值为 21 = 2 的元素 30 还要大,因此继续与索引值为 2i + 1 = 21 + 1 = 22 = 4 的元素做比较。
●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
47 > 38
由于查找的元素 47 比索引值为 22 = 4 的元素 38 还要大,因此继续与索引值为 2i + 1 = 22 + 1 = 23 = 8 的元素做比较。
●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
47 < 79
由于查找的元素 47 比索引值为 23 = 8 的元素 79 还要小,因此我们可以知道如果查找的元素 47 要存在于该串行中的话,其索引值必定会在 22 + 1 ~ 23 - 1 的范围中,也就是 5 ~ 7。接着再针对这个范围做二元搜索法即可。
● ○ ●
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
47 < 61
◎
索引 0 1 2 3 4 5 6 7 8 9
数值 2 9 30 32 38 47 61 69 79 81
47 == 47
如此一来便可以发现元素 47 存在串行中索引值为 5 的位置。若要搜索的元素在串行中愈前面的话,就可以愈快被搜索到。

指数搜索法的程序实作
/// 指数搜索法。
pub fn exponential_search(array: &[i32], target_element: i32) -> Option<usize> {
let length = array.len();
if length == 0 {
None
} else if target_element == array[0] {
Some(0)
} else {
let mut two = 1;
while two < length {
match target_element.cmp(&array[two]) {
Ordering::Equal => {
return Some(two);
}
Ordering::Less => {
return binary_search(array, target_element, (two >> 1) + 1, two - 1);
}
Ordering::Greater => {
two <<= 1;
}
}
}
binary_search(array, target_element, (two >> 1) + 1, length - 1)
}
}
/// 二元搜索法,使用循环来迭代。
pub fn binary_search(array: &[i32], target_element: i32, mut start: usize, mut end: usize) -> Option<usize> {
while end >= start {
let middle = start + ((end - start) >> 1);
match target_element.cmp(&array[middle]) {
Ordering::Equal => {
return Some(middle);
}
Ordering::Greater => {
start = middle + 1;
}
Ordering::Less => {
if middle > 0 {
end = middle - 1;
} else {
break;
}
}
}
}
None
}
/**
* 指数搜索法。
*/
public static int exponentialSearch(final int[] array, final int targetElement) {
final int length = array.length;
if (length == 0) {
return -1;
}
if (targetElement == array[0]) {
return 0;
}
int two = 1;
while (two < length) {
if (targetElement == array[two]) {
return two;
} else if (targetElement < array[two]) {
return binarySearch(array, targetElement, (two >> 1) + 1, two - 1);
}
two <<= 1;
}
return binarySearch(array, targetElement, (two >> 1) + 1, length - 1);
}
/**
* 二元搜索法,使用循环来迭代。
*/
public static int binarySearch(final int[] array, final int targetElement, int start, int end) {
while (end >= start) {
final int middle = (end + start) >>> 1;
if (targetElement == array[middle]) {
return middle;
} else if (targetElement > array[middle]) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return -1;
}
/**
* 指数搜索法。
*/
function exponentialSearch(array: number[], targetElement: number) {
const length = array.length;
if (length === 0) {
return -1;
}
if (targetElement === array[0]) {
return 0;
}
let two = 1;
while (two < length) {
if (targetElement === array[two]) {
return two;
} else if (targetElement < array[two]) {
return binarySearch(array, targetElement, (two >> 1) + 1, two - 1);
}
two <<= 1;
}
return binarySearch(array, targetElement, (two >> 1) + 1, length - 1);
}
/**
* 二元搜索法,使用循环来迭代。
*/
function binarySearch(array: number[], targetElement: number, start: number, end: number) {
while (end >= start) {
const middle = start + ((end - start) >> 1);
if (targetElement === array[middle]) {
return middle;
} else if (targetElement > array[middle]) {
start = middle + 1;
} else {
end = middle - 1;
}
}
return -1;
}
// 指数搜索法。
func ExponentialSearch(array []int, targetElement int) int {
length := len(array)
if length == 0 {
return -1
}
if targetElement == array[0] {
return 0
}
two := 1
for two < length {
if targetElement == array[two] {
return two
} else if targetElement < array[two] {
return BinarySearch(array, targetElement, (two>>1)+1, two-1)
}
two <<= 1
}
return BinarySearch(array, targetElement, (two>>1)+1, length-1)
}
// 二元搜索法,使用循环来迭代。
func BinarySearch(array []int, targetElement int, start int, end int) int {
for end >= start {
middle := int(uint(end+start) >> 1)
if targetElement == array[middle] {
return middle
} else if targetElement > array[middle] {
start = middle + 1
} else {
end = middle - 1
}
}
return -1
}
左位移一个比特等同于「乘以 2」;右位移一个比特等同于「除以 2」。
指数搜索法的复杂度
以 #{{n}}# 来表示要搜索的数据笔数。
| 项目 |
值 |
备注 |
| 最差时间复杂度 |
#{{O(\log n)}}# |
|
| 最佳时间复杂度 |
#{{O(1)}}# |
要查找的元素刚好位于串行的最前面。 |
| 平均时间复杂度 |
#{{O(\log n)}}# |
|
| 最差空间复杂度(递归的二元搜索法) |
#{{O(\log n)}}# |
|
| 最差空间复杂度(迭代的二元搜索法) |
#{{O(1)}}# |
|