斐波那契查找

和二分查找和插值查找类似,就是mid的选取概念不一样,斐波那契查找是选用黄金分割点.如下图,是一次选取mid点的流程

整体代码

import java.util.Arrays;

public class FebonacciSearch {
    static int[] Febo;
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,17,9869};
        System.out.println(febonacciSearch(arr,9868));
    }
    public static int[] makeFebo(int len){
        Febo = new int[len];
        Febo[0] = 1;
        Febo[1] = 1;
        for (int i = 2; i < len; i++) {
            Febo[i] = Febo[i-1] + Febo[i-2];
        }
        return Febo;
    }
    public static int febonacciSearch(int[] arr,int target){
        int left = 0;//查找的左边界
        int right = arr.length - 1;//查找的有边界
        int mid;//mid
        int n = 0;//febo的下标
        //febo的长度没有必要那么大,所以简单用(arr.length + 4) / 2,其实应该根据实际情况设计
        int[] febo = makeFebo((arr.length + 4) / 2);
        while (febo[n] - 1 <= right){
            n++;
        }
        //假如arr.lenth没febo[n]大,那就用最大值来填充
        //原数组不能直接填充,所以克隆一个出来
        int[] clone = Arrays.copyOf(arr, febo[n]);
        //补齐长度,用arr[right],即最大值填充
        for (int i = right + 1; i < clone.length; i++) {
            clone[i] = arr[right];
        }
        //开始循环
        //只要左边界小于等于右边界,就可以继续循环
        while (left <= right){
            //计算mid
            mid = left + febo[n-2] - 1;
            if (clone[mid] == target){
                //需要判断mid是填充出来的,还是数组本身的,
                //针对最大值,需要取最小索引
                return Math.min(mid, right);
            }else if(clone[mid] > target){
                //如果大于target,目标应该在左侧
                right = mid - 1;
                //n-=2,因为我们左半边是febo[n-2]个数
                n-=2;
            }else{
                left = mid + 1;
                //n--,因为右半边是febo[n-1]个
                n--;
            }
        }
        return -1;
    }
}