指数搜索(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 的位置。若要搜索的元素在串行中愈前面的话,就可以愈快被搜索到。

指数搜索的过程动画

指数搜索法的程序实作

左位移一个比特等同于「乘以 2」;右位移一个比特等同于「除以 2」。

指数搜索法的复杂度

以 #{{n}}# 来表示要搜索的数据笔数。

项目 值 备注
最差时间复杂度 #{{O(\log n)}}#
最佳时间复杂度 #{{O(1)}}# 要查找的元素刚好位于串行的最前面。
平均时间复杂度 #{{O(\log n)}}#
最差空间复杂度(递归的二元搜索法) #{{O(\log n)}}#
最差空间复杂度(迭代的二元搜索法) #{{O(1)}}#