3、斐波那契搜索中值搜索

中值查找

图片.png

特点： 在连续的数组中可以一次命中目标

关键代码

        // 对比上面图求出中值
        leftv := float64(data - arr[low]) // 大段
        allv := float64(arr[hight] - arr[low]) // 整段
        diff := float64(hight - low)
        //mid := int( float64(low) + leftv/allv*diff ) // 计算中间值
        mid := int( float64(low) + allv * leftv / diff ) // 计算中间值

全部代码

package main
import "fmt"

// 中值搜索
func binSearchMid(arr []int, data int) int {
    low, hight := 0, len(arr)-1 // 找到最左和最右下标
    i:=0
    for low <= hight {
        i++
        fmt.Println("第N次循环", i)

        //mid := (hight + low)/2

        leftv := float64(data - arr[low]) // 大段
        allv := float64(arr[hight] - arr[low]) // 整段
        diff := float64(hight - low)
        //mid := int( float64(low) + leftv/allv*diff ) // 计算中间值
        mid := int( float64(low) + allv * leftv / diff ) // 计算中间值


        if data > arr[mid] {
            low = mid + 1
        } else if data < arr[mid] {
            hight = mid - 1
        } else {
            return mid
        }
    }
    return -1
}


func main()  {
    //arr := make([]int, 1000, 1000)
    arr := []int{2, 3, 4, 5, 6, 7, 8, 9, 10}
    //for i:=0; i<len(arr)-1; i++ {
    //  arr[i] = i
    //}
    //fmt.Println(arr)

    index := binSearchMid(arr, 8)
    //index := binSearch(arr, 7)
    if index == -1 {
        fmt.Println("没找到！")
    } else {
        fmt.Printf("找到数据%d, 下标为%d。", arr[index], index)
    }
}