插值搜索是对二分搜索的改进，在二分搜索中，排序数组中的值是均匀分布的。二分搜索总是转到中间元素进行检查。另一方面，插值搜索可能会根据被搜索键的值转到不同的位置。这是使用插值搜索算法搜索整数数组中元素的Go程序的源代码。输出显示元素在数组中的位置。

示例代码：

package main
import "fmt"

func interpolationSearch(array []int, key int) int {

	min, max := array[0], array[len(array)-1]

	low, high := 0, len(array)-1

	for {
		if key < min {
			return low
		}

		if key > max {
			return high + 1
		}

		// 尝试预测位置var guess int
		if high == low {
			guess = high
		} else {
			size := high - low
			offset := int(float64(size-1) * (float64(key-min) / float64(max-min)))
			guess = low + offset
		}

		// 确认是否找到if array[guess] == key {
			// scan backwards for start of value range
			for guess > 0 && array[guess-1] == key {
				guess--
			}
			return guess
		}

		// 预测位置的数大于key，或小于key修改high，low继续搜索if array[guess] > key {
			high = guess - 1
			max = array[high]
		} else {
			low = guess + 1
			min = array[low]
		}
	}
}


func main(){
	items := []int{1,2, 9, 20, 31, 45, 63, 70, 100}
	fmt.Println(interpolationSearch(items,63))
}

输出：

6