繼續使用猜數字當範例， 1 ~ 100 的數字，但是這次你已經知道結果了，你如果還是繼續使用二元搜尋法，那麼效率不會那麼好，那我們該用甚麼方式解決呢？
概念
插補搜尋法 (Interpolation Search)：是一個基於二元搜尋法的演算法，被搜尋的清單是需要事先先被排序過的，而且資料的分布狀態最好是呈現線性的，如果不是呈現線性分布，那麼在搜尋的過程中，將有可能會得到 O(n) 的結果，可能會比二元搜尋法還更耗時。
公式： lowIndex + (target - array[lowIndex]) * (highIndex-lowIndex) / (array[highIndex] - array[lowIndex])
- lowIndex: 低位索引
- highIndex: 高位索引
- target: 要查找的目標數值
複雜度
- 時間複雜度： O(n)
- 空間複雜度： O(1)
範例
Go
package main
import "fmt"
func interpolationSearch(list []int, target int) int {
low := 0
high := len(list) - 1
for high >= low {
i := low + (target-list[low])*(high-low)/(list[high]-list[low])
if i > high || i < low {
break
}
if target == list[i] {
return i
} else if target > list[i] {
low = i + 1
} else {
high = i - 1
}
}
return -1
}
func main() {
fmt.Println(interpolationSearch([]int{1, 2, 3, 4, 5}, 3)) // 2
fmt.Println(interpolationSearch([]int{1, 2, 3, 4, 5}, 6)) // -1
}
C#
class Algorithm
{
public static int interpolationSearch(int[] list, int target)
{
var low = 0;
var high = list.Length - 1;
while (high >= low)
{
var i = low + (target - list[low]) * (high - low) / (list[high] - list[low]);
if (i > high || i < low)
{
break;
}
if (target == list[i])
{
return i;
}
else if (target > list[i])
{
low = i + 1;
}
else
{
high = i - 1;
}
}
return -1;
}
public static void Main(String[] args)
{
Console.WriteLine(interpolationSearch(new int[] {1, 2, 3, 4, 5}, 3)); // 2
Console.WriteLine(interpolationSearch(new int[] {1, 2, 3, 4, 5}, 6)); // -1
}
}
歡迎到我的 Facebook Alan 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。