什么是斐波那契数列

斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、…,在数学上,斐波那契被递归方法如下定义:F(1)=1,F(2)=1,F(n)=f(n-1)+F(n-2)（n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）。

斐波那契查找介绍

斐波那契搜索(Fibonacci search) ，又称斐波那契查找，是区间中单峰函数的搜索技术。斐波那契搜索就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为F[n]-1（如果要补充元素，则补充重复最后一个元素，直到满足F[n]个元素），完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]-1个元素，后半部分F[n-2]-1个元素，找出要查找的元素在那一部分并递归，直到找到。

思路分析

代码实现

package com.why.search;

import java.util.Arrays;

public class FeiBoSearch {

    public static int maxSize = 20; //斐波那契数列初始长度

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9};
        int index = feiboSearch(arr, 5);
        System.out.println(index==-1?"找不到元素":"目标元素的下标为"+index);
    }

    /**
     * 初始化斐波那契数列
     * @return 斐波那契数列
     */
    public static int[] feibo(){
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i <f.length ; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        return f;
    }

    /**
     * 斐波那契搜索
     * @param arr 要搜索的数组
     * @param target 目标元素
     * @return 元素在数组中的下标
     */
    public static int feiboSearch(int[] arr,int target){
        int low = 0;
        int mid = 0;
        int n = 0;
        int high = arr.length-1;
        int[] f = feibo(); //这里待优化 实现数组自动扩容

        //在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]
        while(high >= f[n] - 1){
            n++;
        }

        //将原查找表扩展为长度为F[n]-1
        int[] temp = Arrays.copyOf(arr, f[n] - 1);

        //填充元素
        for (int i = high+1; i < temp.length; i++) {
            temp[i] = temp[high];
        }

        while(low <= high){
            mid = low + f[n-1]-1;
            if (target < temp[mid]){
                //继续查找mid左边的数列
                high = mid-1;
                n--;
            }else if (target > temp[mid]){
                //继续查找mid右边的数列
                low = mid+1;
                n -= 2;
            }else {
                if (mid <= high){
                    return mid;
                }else {
                    return high;
                }
            }
        }
        //找不到目标元素
        return -1;
    }
}

结果输出

目标元素的下标为4

Process finished with exit code 0