Aloha！又是我是少女人妻 Uerica！白天樓上常常會施工，鑽地板跟敲打的聲音總是讓人難以忍受，總算有天受不了了，我就開始告訴自己這些聲音是把一張張鈔票用力的鑽到我的存款中，所以每個聲響都代表錢錢入帳！從此之後我開始會期待樓上施工，一天沒施工我還會擔心，今天不發薪水嗎～XD

好的～要繼續昨日的搜尋演算法了！

指數搜尋法 Exponential Search

指數搜尋法又稱雙倍搜尋法 Doubling Search 或 蔓延搜尋法 Galloping Search ，指數搜尋法其實也是二分搜尋法的演變，專門用在搜尋已排列好但資料量無限大的數列中。與二分搜尋法不同的是，指數搜尋法不是從數列中間開始搜尋，而是利用指數成長的方式搜尋到資料元素可能若在的範圍，再用二分搜尋法來找尋。

指數搜尋法 Exponential Search 操作圖解

• 假設在下列排序過的數列中要找到數值 49 的位置
  

• 用指數增加來搜尋，因 2 ^ 0 = 1，所以先搜尋索引值 1 的位置。
  

• 因 49 > 7 ，表示欲搜尋的目標索引值會比索引值 1 還大，所以因 2 ^ 1 = 2 ，搜尋下一個索引值 2 的位置
  

• 因 49 > 12 ，表示欲搜尋的目標索引值會比索引值 2 還大，所以因 2 ^ 2 = 4 ，搜尋下一個索引值 4 的位置
  

• 因 49 > 33 ，表示欲搜尋的目標索引值會比索引值 4 還大，所以因 2 ^ 3 = 8 ，搜尋下一個索引值 8 的位置
  

• 因 49 < 62 ，表示欲搜尋的目標索引值會落在索引值 2 ^ 2 = 4 與索引值 2 ^ 3 = 8之間，所以欲搜尋的目標會在小於索引值 4 (包含 4 )、大於索引值 8 (包含 8 )的數列中。
  

• 此時再用二分搜尋法來搜尋，先取數列的中間值來比對。
  

• 因 49 < 51 ，往前找到索引值 5 ，比對後找到搜尋目標～
  

內插搜尋法 Interpolation Search

內插搜尋法又稱為插捕搜尋法，也是從二元搜尋法 Binary Search 演變而來。搜尋的數列必須是已排序過的數列，再利用數學中的線性插值法來計算出欲搜尋元素的索引值來找到元素，適合用來搜尋資料量大、數值平均成長的數列。

線性插值法 Linear Interpolation
數學中的內插法 (或稱插值法)，其中一種最簡單的方法就是線性插值法，簡單來說就是假設一筆數值是線性成長，並利用數值近似線的特性求得其中 x 或 y 的值。

如下圖可以看到，假設是一個線性成長的數列，若 x 軸為索引值、y 軸為資料元素(數值)， x1 與 y1 表示第一個索引值與儲存在內的數值，x2 與 y2 可表示最後一個索引值與儲存在內的數值，而 x 與 y 則表示欲搜尋的索引值與數值。依照圖示可以求得右上角公式。

• (y-y1)/(x-x1) = (y2-y1)/(x2-x1)

從上列公式推出 x 值的求法，因欲搜尋某數值會知道該數值的值 (y)，而不知道其索引值 (x)，所以若想找到該數值在哪裡，就要知道其索引值在哪裡。

• x 就是欲搜尋資料的索引值
• 求得公式為 x = (y-y1)(x2-x1)/y2-y1 + x1
  

內插搜尋法 Interpolation Search 操作圖解

• 假設在下列排序過的數列中一樣要找數值 49 在哪個位置
  

• 利用上述公式求 x = (49 - 1) * (8 - 0) / (62 - 1) + 0 = 6.29，無條件捨去取整數 6 ，搜尋索引值 6 的位置
  

• 因 49 < 56 ，表示搜尋目標的索引值小於索引值 6，將 x2 與 y2 設為索引值 6 數值 51 ，再利用公式求得 x = (49 - 1) * (6 - 0) / (51 - 1) + 0 = 5.76，無條件捨去取整數 5 ，搜尋索引值 5 的位置
  

• 因 49 < 51 ，搜尋索引值 5 數值，找到搜尋目標 ～
  

參考資料：

維基百科 - 線性插值

插補搜尋(Interpolation Search)演算法，運用資料近似線來輔助搜尋的演算法

內插搜尋 Interpolation Search

JavaScript 學演算法（二十）- 搜尋演算法

好的～今天就到這邊啦！祝福大家發財～掰掰