golang如何实现插值搜索？

下载万磁搜索绿色版

在Golang实战开发的过程中，我们经常会遇到一些这样那样的问题，然后要卡好半天，等问题解决了才发现原来一些细节知识点还是没有掌握好。今天golang学习网就整理分享《golang如何实现插值搜索？》，聊聊golang、插值搜索，希望可以帮助到正在努力赚钱的你。

问题内容

golang如何实现插值搜索？

正确答案

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  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 {
			// 扫描后面的
			for guess > 0 && array[guess-1] == key {
				guess--
			}
			return guess
		}

		// 判断高还是低
		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))
}

到这里，我们也就讲完了《golang如何实现插值搜索？》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于golang的知识点！