为了更好地理解这个示例，我们始终建议您学习下面列出的 Golang 编程 的基础主题
有不同类型的搜索算法。但本节我们将讨论一种对传统二分搜索方法进行改进的方法，称为插值搜索。这里我们将解释如何编写一个 GO 程序来使用插值搜索从数组中搜索一个元素。
插值搜索算法和二分搜索算法的主要区别在于，二分搜索从数组的中间开始搜索。而插值搜索算法则尝试在元素更可能存在的位置查找。为了算法的正常工作，数组的元素必须是排序且均匀分布的。
插值搜索与在电话簿中搜索特定姓名或在英语词典中搜索特定单词几乎相似，数据必须均匀分布。例如，在电话簿中，所有以a或b开头的姓名将位于目录的开头，而所有以o和p开头的姓名可能位于中间。另一方面，以x、y和z开头的姓名将位于目录的末尾。因此，我们可以根据我们需要搜索的元素，每次在不同的位置开始搜索。
在一个均匀分布的已排序数组中，较小的数字将位于数组的开头，而较大的数字应位于数组的末尾。因此，每当插值搜索想要从这个数组中搜索一个较大的数字时，它将从数组的末尾开始搜索，而对于较小的数字，它将从数组的开头开始搜索。
在这个 GO 程序中，我们导入了“fmt”包，以在程序中包含一些标准库。之后主函数开始，在主函数内部，我们执行整个程序。请注意，插值搜索算法的时间复杂度为 Ο(log (log n))。
在这个GO程序中，我们使用fmt包中定义的fmt.scanln()和fmt.println()方法来接收用户输入的值。为了使用这些函数，我们需要导入“fmt”包。
这里变量A存储数组元素。其他变量n和key分别用作数组的大小和要搜索的元素。使用for循环读取数组元素。请注意，插值搜索仅在元素按均匀分布的排序顺序排列时才有效。
变量 low 和 high 用作函数参数。赋值 low = 0, high = n-1，并通过调用函数 InterpolationSearch(A,key) 在迭代循环中执行插值搜索，并将函数返回值赋给变量 index。这里我们使用以下公式计算中间元素 mid：
mid = low + ((key – A[low]) * (high – low) / (A[high] – A[low]))
其中 A[low...high] 是我们的搜索空间，而 key 是给定的要搜索的元素。
如果搜索元素 key 与中间元素匹配，则返回中间元素的索引。否则，检查 key 是否大于中间元素。如果是，则将 low = mid + 1。否则，将 high = mid – 1。如果索引等于 -1，则打印“Element not found”。否则，打印找到的元素的索引，即 index + 1。
下面是Go程序中实现插值搜索的步骤。
步骤1：导入fmt包
步骤2：打开main()开始程序，GO程序执行从main()开始
步骤3：声明变量n、x、temp、Low、High和result。
步骤4：将数组大小读取为n。
步骤5：定义数组 A[]。
步骤6：使用for循环读取A[]数组元素。
步骤7：读取要搜索的数字作为键。
步骤8：将 Low 赋值为 0，将 High 赋值为项数 n-1。
步骤9：调用函数 InterpolationSearch(A, key) 并将返回值赋给 index。
步骤10：使用“if”条件检查索引是否等于-1。如果是，则打印“Element not found”。
步骤11：否则，打印找到的元素的位置。即：index + 1
步骤12：退出
步骤1：声明变量mid为中间元素，low和high为数组索引。
步骤2：初始化 low = 0 和 high = n-1。
步骤3：打开“for循环”并检查条件 A[low] < key 和 A[high] > key。如果条件为真，则执行以下步骤。
步骤4：使用公式计算中间元素 mid：mid = low + ((key-A[low])*(high-low))/(A[high]-A[low])。
步骤5：使用“if”条件检查搜索元素键是否等于数组中间元素mid。如果是，则返回mid的值并退出此函数。
步骤6：使用“if”条件检查数组中间元素mid是否小于键。如果是，则将low = mid + 1。
步骤7：否则，检查数组中间元素mid是否大于键，如果是，则high = mid - 1。
步骤8：使用“if”条件检查搜索元素key是否等于数组中间元素mid。如果是，则返回mid的值并退出此函数。
步骤9：检查 A[low] 是否等于搜索元素 key，如果是，则返回 low。
步骤10：否则检查 A[high] 是否等于搜索元素 key，如果是，则返回 high。否则返回 -1。
下面是使用插值搜索算法在整数数组中搜索元素的Go程序源代码。输出将显示元素在数组中的位置。
package main
import "fmt"
//interpolation search method
func InterpolationSearch(A []int, key int)int{
var mid int
var low int
low = 0
var high int
high = len(A) - 1
for A[low] < key && A[high] > key {
mid = low + ((key-A[low])*(high-low))/(A[high]-A[low])
if A[mid] < key {
low = mid + 1
} else if A[mid] > key {
high = mid - 1
} else {
return mid
}
}
if A[low] == key {
return low
} else if A[high] == key {
return high
} else {
return -1
}
}
// main method
func main() {
var key int
var n int
fmt.Println("Enter the size of the array")
fmt.Scan(&n)
A := make([]int, n, 100)
fmt.Println("Enter elements of the array in uniform distributed and sorted order: ")
for i := 0; i < n; i++ {
fmt.Scan(&A[i])
}
fmt.Println("Enter the number to be searched")
fmt.Scan(&key;)
var index int
index = InterpolationSearch(A, key)
if index == -1 {
fmt.Println("Element not found !")
} else {
fmt.Println("The element found at", index+1)
}
}
Enter the size of the array 5 Enter elements of the array in uniform distributed and sorted order: 2 4 6 8 10 Enter the number to be searched 8 The element found at 4
