擁抱「資料結構」的「演算法」(26) - 內插搜尋法

 

前言

今天要來介紹內插搜尋法,這個名字聽起來就很抽象,不容易知道這個演算法是如何進行搜尋的,一起來認識它吧!


生活常識

唸大學的時候,如果可以自由挑選座位,你都是做在哪邊的位置上呢?是挑前面的位置認真上課,還是挑後面的位置方便翹課XD,想必你對於坐前面或坐後面有一套自己的挑選方式,而如果是站在授課老師的角度,老師會挑選前面的學生來回答問題,還是挑後面的學生來回答問題呢?如何在教室內挑到一位合適的學生來回答不同難易程度的問題,這真的是很考驗老師的搜尋能力,感覺坐越前面參與度越高,越後面參與度越低,到底要挑選哪一區的哪一位同學來回答,想必老師也有一套挑選學生的方式


圖片來源:https://www.pexels.com/zh-tw/photo/207691/


專業知識 - 內插搜尋法 Interpolation Search

內插搜尋法又稱插補搜尋法,主要是針對已排序的資料進行搜尋,算是二分搜尋法的改良版本,二分法會先找中間值,但內插搜尋法會透過斜率公式初步估算資料可能出現在哪個的位置,很像在一個範圍插入一個可能的位置,並逐漸縮小搜尋範圍

斜率公式可參考維基百科


圖片來源:https://zh.wikipedia.org/wiki/%E6%96%9C%E7%8E%87

插補搜尋法公式

假設 X 軸為陣列索引Y 軸由小到大排列的儲存的數值,我們可藉由終點(x2, y2)與起點(x1, y1)的斜率會等於目標點(x-key, y-value)與起點(x1, y1)的斜率`去推出資料可能的位置



例子

有一數列:1, 22, 32, 48, 56, 63, 47, 82, 94,共 9 個數值,由小到大排列,要找 48 在哪裡,套用公式時,若求出來的值有小數點則四捨五入(或使用你習慣的方式處理小數點也可以),以下分為兩個步驟進行搜尋:

  1. 第一次的公式代入得到 X 軸 = 4 ,則去找陣列索引 4 的位置,找到的數值為 56 ,56 不等於 48,繼續搜尋
  2. 第二次的公式代入,得到數值 X 軸 = 3,則去找陣列索引 3 的位置,找到的數值為 48 ,48 等於 48,成功找到數值則結束搜尋



分析

效能的好壞取決於數值的分佈,如果資料分佈的越平均,搜尋速度就越快,

  • 最壞的情況
    O(n),資料分佈不平均

  • 最好的情況
    Ο(log2n),每次搜尋可減少一半的資料量


今日小結

內插搜尋法在資料分佈均勻時真的蠻快的,但分佈不均勻時跟循序搜尋法差不多,要特別注意資料的分佈情況是否均勻


今日謎題

123456 = 1 這個等式是錯的,你知道如何在 12、3、4、5、6 之間插入四個運算符號(只能用加號、減號或乘號),使等式成立嗎

昨日解謎

謎題說明:主要是希望大家可以體會一下二分搜尋法中對半切動作,將下圖資料對半切,然後只看右半部,就可以觀察到 2576 這四個數字,你猜對了嗎?



留言

這個網誌中的熱門文章

CPE 一顆星選集題目說明與解答 - Java 筆記與心得分享

Visual Studio 自動排版格式化程式碼

1. Vito's family (CPE10406, UVA10041) - CPE一顆星解答與說明