/*
1、拉格朗日中值:减少比较次数
left mid data right
------------------------------------------------------------
一般求mid:mid=(left+right)/2
可以转换为:
mid = left + (right-left)/2
mid = left + (right-left) * 1/2
如果待查找的值的下标为 data
mid = left + (right-left) * (data-left)/(right-left) (比例)
*/
func bin_searchMid(arr []int,data int) int {
low := 0
high := len(arr)-1
i := 0
for low<= high{
i++
fmt.Println("第N次",i)
leftv := float64(data-arr[low]) // 大段
allv := float64(arr[high]-arr[low])//整段
diff := float64(high-low) // 比例
mid := int(float64(low)+leftv/allv*diff) //计算中间的值
//mid := (low+high)/2
if mid <0 || mid >= len(arr){
return -1
}
if arr[mid] > data {
high = mid -1
}else if arr[mid] < data{
low = mid +1
}else {
return mid
}
}
return -1
}
网友评论