package com.xcc.dataStructures.demo07_search;

import java.util.Arrays;

/**
 * 斐波那契查找算法
 *
 * @author xiaocheng
 * @date 2020/12/9 15:53
 */
public class FibonacciSearch {

    private static Integer size = 10;

    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};
        System.out.println(fibonacciSearch(arr, 1235));
    }

    /**
     * 定义斐波拉契数组
     */
    public static int[] fib() {
        if (size < 2) {
            throw new RuntimeException("定义的数组长度必须大于2");
        }
        int[] f = new int[size];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < size; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    /**
     * 查找
     */
    public static int fibonacciSearch(int[] arr, int val) {
        int left = 0;
        int right = arr.length - 1;
        int[] f = fib();
        int k = 0;
        while (right > f[k] - 1) {
            k++;
        }
        //拷贝临时数组  比原始数组长的部分会直接用0补齐
        int[] temp = Arrays.copyOf(arr, f[k]);
        //将长于arr部分用高位值补齐
        for (int i = right + 1; i < temp.length; i++) {
            temp[i] = arr[right];
        }
        int mid = 0;
        while (left <= right) {
            mid = left + f[k - 1] - 1;
            if (val < temp[mid]) {
                //向左找
                right = mid - 1;
                k--;
            } else if (val > temp[mid]) {
                //向右找
                left = mid + 1;
                k -= 2;
            } else {
                if (mid < right) {
                    return mid;
                } else {
                    //如果查到的是扩容之后的数值，就直接返right
                    return right;
                }
            }

        }
        return -1;
    }

}