【在厨房想30天的演算法】Day 18 演算法 : 搜寻 search II 指数搜寻、内插搜寻

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 学演算法（二十）- 搜寻演算法

好的～今天就到这边啦！祝福大家发财～掰掰