斐波那契中值搜索

 func makeFabArray(arr []int) []int{
    length := len (arr)
    flblengh := 2
    first,second,third := 1,2,3
    for third < length { //找出最接近的
        third,first,second = first+second,second,third // 叠加计算斐波那契
        flblengh++
    }

    //开辟斐波那契数组
    fb := make([]int,flblengh)
    fb[0]=1
    fb[1]=1
    for  i:=2; i < flblengh;i++{
        fb[i]=fb[i-1]+fb[i-2]
    }
    return fb
 }


 /*

斐波那契查找，首先得弄明白什么是斐波那契数列。相信大家对这个著名的数列也并不陌生，无论是C语言的循环、递归，还是高数的数列，斐波那契数列都是一个重要的存在。而此处主要是用到了它的一条性质：前一个数除以相邻的后一个数，比值无限接近黄金分割。

就笔者而言，这种查找的精髓在于采用最接近查找长度的斐波那契数值来确定拆分点,初次接触的童鞋，请在读完下文后，自觉回过头来仔细体会这句话。举个例子来讲，现有长度为9的数组，要对它进行拆分，对应的斐波那契数列（长度先随便取，只要最大数大于9即可）
 {1，1，2，3，5，8，13，21，34}，不难发现，大于9且最接近9的斐波那契数值是f[6]=13，为了满足所谓的黄金分割，所以它的第一个拆分点应该就是f[6]的前一个值f[5]=8，即待查找数组array的第8个数，对应到下标就是array[7]，依次类推。

推演到一般情况，假设有待查找数组array[n]和斐波那契数组F[k],并且n满足n>=F[k]-1&&n < F[k+1]-1，则它的第一个拆分点middle=F[k]-1。

这里得注意，如果n刚好等于F[k]-1,待查找数组刚好拆成F[k-1]和F[k-2]两部分，那万事大吉你好我好；然而大多数情况并不能尽人意，n会小于F[k]-1,这时候可以拆成完整F[k-1]和残疾的F[k-2]两部分，那怎么办呢？

聪明的前辈们早已想好了解决办法，对了，就是补齐，用最大的数来填充F[k-2]的残缺部分，如果查找的位置落到补齐的部分，那就可以确定要找的那个数就是最后一个最大的了。
  */
func fab_search(arr []int,val int) int  {
    length := len(arr)
    fabArr := makeFabArray(arr) //定制匹配的斐波那契数组
    fmt.Println("fabArr:",fabArr)
    filllength := fabArr[len(fabArr)-1]  //填充长度

    fillArr := make([]int,filllength)//填充的数组
    for i,v := range arr{
        fillArr[i]=v
    }

    lastdata := arr[length-1]//填充最后一个大数
    for i:=length; i < filllength; i++{
        fillArr[i] = lastdata //填充数据
    }
    fmt.Println(fillArr,length) //填充以后的数组

    left,mid,right := 0,0,length //类似二分查找
    kindex := len(fabArr)-1 //游标

    for left <= right {
        //斐波那契黄金切割  斐波那契的middle = low + F[k-1] -1
        mid = left + fabArr[kindex-1]-1
        if val < fillArr[mid]{
            right = mid-1
            kindex--
        }else if val > fillArr[mid]{
            left = mid+1
            kindex-=2
        }else {
            if mid > right {
                return right  //越界
            }else {
                return mid
            }
        }
    }
    return -1
}