指數搜尋(Exponential Search)演算法又稱為雙倍搜尋(Doubling Search)演算法或是蔓延搜尋(Galloping Search)演算法,是二元搜尋(Binary Search)演算法的變體。這套演算法可以在已排序好的序列中進行高效率的搜尋,要搜尋的元素在序列中愈前面的話,搜尋效能愈好。



指數搜尋法(Exponential Search)

指數搜尋法的概念

指數搜尋法是基於二元搜尋法的演算法,如果您還不了解二元搜尋法的話,請先參考這篇文章:

https://magiclen.org/binary-search/

指數搜尋法與二元搜尋法的差異在於,它在一開始的時候,並不是直接去選擇序列中間的元素來比較,而是先去比較索引值為20 = 1的元素。如果發現要查找的元素比索引值為20的元素還要小,表示要查找的元素不是在索引值0的位置上,要不然就是不在序列中;如果要查找的元素比索引值為20的元素還要大,表示要查找的元素可能會出現在索引值為20之後,此時再繼續比較要查找的元素與索引值為20 + i = 2i的元素,i1, 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的元素47還要小,因此我們可以知道如果查找的元素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的位置。若要搜尋的元素在序列中愈前面的話,就可以愈快被搜尋到。

exponential-search

指數搜尋法的程式實作

指數搜尋法的複雜度

以#{{n}}#來表示要搜尋的資料筆數。

項目備註
最差時間複雜度#{{O(\log n)}}#
最佳時間複雜度#{{O(1)}}#要查找的元素剛好位於序列的最前面。
平均時間複雜度#{{O(\log n)}}#
額外最差空間複雜度(遞迴的二元搜尋法)#{{O(\log n)}}#
額外最差空間複雜度(迭代的二元搜尋法)#{{O(1)}}#