Introduce

黄金分割查找，区别于插值查找找0.5，斐波那契查找找0.618。

image.png

原理介绍

image.png

推导得出只要顺序数组长度=F[k]-1,就可将数组分为两部分，一部分长度F[k-1],一部分F[k-2]

此时mid=low+F[k-1]-1;

需要注意的是，顺序数组长度不一定=F[k]-1，所以需要对原数组扩容，让其满足该条件

image.png

code

package com.pl.arithmetic.search;

import java.util.Arrays;

/**
 * <p>
 *
 * @Description: TODO
 * </p>
 * @ClassName FibonacciSearch
 * @Author pl
 * @Date 2020/12/30
 * @Version V1.0.0
 */
public class FibonacciSearch {

    public static int maxSize = 20;
    public static void main(String[] args) {
        int [] arr = {1,8, 10, 89, 1000, 1234};

        System.out.println("index=" + fibSearch(arr, 1234));// 0

    }

    /**
     * 构建斐波那契数组
     * 
     * @param 
     * @return int[]
     * @exception 
     * @author silenter
     * @date 2020/12/30 7:51
    */
    public static int[] buildFibArr(){
        int[] arr = new int[maxSize];
        arr[0] = 1;
        arr[1] = 2;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i-1]+arr[i-2];
        }
        return arr;
    }

    /**
     *斐波那契查找法
     * 
     * @param oriArr
     * @param target
     * @return int
     * @exception 
     * @author silenter
     * @date 2020/12/30 7:51
    */
    public static int fibSearch(int[] oriArr, int target) {
        int arrLength = oriArr.length;
        int[] fibArr = buildFibArr();
        int fibIndex = 0;
        //todo 寻找数组的长度接近的那个斐波那契元素，创造一个长度=fibArr[fibIndex]-1长度的数组,因为只有满足这个条件,才有mid = low + fibArr[fibIndex-1]-1
        while (arrLength>fibArr[fibIndex]-1){
            fibIndex++;
        }
        //数组长度不一定=fibArr[fibIndex]-1  所以需要扩容{1,8, 10, 89, 1000, 1234, 0, 0}
        int[] fiboriArr = Arrays.copyOf(oriArr, fibArr[fibIndex]);
        //因为数组为顺序数组，需要将0改成最大值
        for (int i = arrLength; i < fiboriArr.length; i++) {
            fiboriArr[i] = oriArr[arrLength-1];
        }
        //todo 在扩容数组中找值
        int mid = 0;
        int leftIndex = 0;
        int rightIndex = oriArr.length-1;
        //注意此时判断条件是原数组的边界比较，因为此时是在扩容数组中寻找，所以允许出现leftIndex = rightIndex，因为有一种情况，一直在右侧查找，有可能到扩容元素中查找
        while (leftIndex<=rightIndex){
            mid =leftIndex+fibArr[fibIndex-1] -1;
            //向左查询
            if (fiboriArr[mid]>target){
                rightIndex = mid-1;
                //此时将数组分为两部分  fibArr[fibIndex]-1(当前数组长度，即fiboriArr.length) = fibArr[fibIndex-1]-1(左部分长度)+fibArr[fibIndex-2]-1（右部分长度）+1（mid算一个长度）
                //此时需要在左部分中查找target，此时左部分数组长度为  fibArr[fibIndex-1]-1 ，mid =fibArr[fibIndex-1-1]-1  所以fibIndex--
                fibIndex--;
            }else if (fiboriArr[mid]<target){
                //此时将数组分为两部分  fibArr[fibIndex]-1(当前数组长度，即fiboriArr.length) = fibArr[fibIndex-1]-1(左部分长度)+fibArr[fibIndex-2]-1（右部分长度）+1（mid算一个长度）
                //此时需要在右部分中查找target，此时右部分数组长度为  fibArr[fibIndex-2]-1 ，mid =fibArr[fibIndex-2-1]-1  所以fibIndex-=2
                leftIndex = mid+1;
                fibIndex-=2;
            }else {
                if (mid<arrLength){
                    return mid;
                }else {
                    return arrLength-1;
                }
            }
        }
        return -1;
    }
}