一、斐波那契查找算法基本思想

斐波那契查找算法又称为黄金分割法查找算法，是一种有序查找算法。

斐波那契数列，又称黄金分割数列，指的是这样一个数列：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）。

斐波那契查找是在二分查找的基础上根据斐波那契数列进行分割。在斐波那契数列找一个等于大于查找表中元素个数的数F(n),将原查找表扩展为长度为F(n)(如果要补充元素，则补充重复最后一个元素，直到满足F(n)个元素)，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F(n-1)个元素，后半部分F(n-2)个元素，找出要查找的元素在那一部分并递归，直到找到。斐波那契查找的时间复杂度是O(log2n)。

斐波那契查找原理与二分查找和插值查找相似，仅仅改变了中间结点mid的位置，mid不再是通过二分或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1（F代表斐波那契数列），如下图所示

对F(k-1)-1的理解：

（1）由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，可以得到 （F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 。该式说明：只要顺序表的长度为F[k]-1，则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段，即如上图所示。从而中间位置为mid=low+F(k-1)-1；
（2）每一子段也可以用相同的方式分割；
（3）若顺序表长度n不一定刚好等于F[k]-1，则需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可。

例如：原数组为{1,5,6,33,55,233,455}，长度n为7，若 F[ k ] - 1等于9，则应该将原数组扩容到9，多出的位置使用high位置的455填充，即得到{1,5,6,33,55,233,455,455,455}。

二、代码实现

斐波拉契查找算法实现思路：

（1）我们需要先递归实现斐波拉契数列，然后根据原数组的大小计算斐波拉契数列的k值；
（2）数组扩容条件是：增大 k 值（索引从 0 开始），使得数组长度刚好大于或者等于斐波那契数列中的 F[k]-1 ，我们定义临时数组 temp ，temp 后面为 0 的元素都按照数组最大元素值填充；
（3）mid值的确定：mid = low + f[k - 1] - 1 ，即用黄金分割点确定 mid 的值；
（4）value<temp[mid] ：目标值在黄金分割点的左边，因为全部元素 = 前面的元素 + 后边元素即 f[k] = f[k-1] + f[k-2]，又前面有 f[k-1]个元素,所以可以继续拆分 f[k-1] = f[k-2] + f[k-3]，即下次循环有mid=low+f[k-1-1]+1，即需要k-=1；
value> temp[mid] ：目标值在黄金分割点的右边。因为全部元素 = 前面的元素 + 后边元素即 f[k] = f[k-1] + f[k-2]，又前面有 f[k-2]个元素,所以可以继续拆分 f[k-1] = f[k-3] + f[k-4]，即下次循环有mid=low+f[k-1-2]+1，即需要k-=2；
value== temp[mid] ：找到目标值，因为数组经历过扩容，后面的值其实有些是多余的，mid 可能会越界（相对于原数组来说）则有：
1）mid <= high ：证明 mid 索引在原数组中，返回 mid；
2）mid > high 时，证明 mid 索引已经越界（相对于原数组来说），返回 high；
（5）若没有找到则返回-1。

package Search;

import java.util.Arrays;
import java.util.Scanner;

public class FibonacciSearch {
	public static final int maxSize=20;//斐波拉契数列的大小
	
	public static int[] fibonacci() {//构造斐波拉契数列
		int[] fib=new int[maxSize];
		fib[0]=1;
		fib[1]=1;
		for(int i=2;i<maxSize;i++) {
			fib[i]=fib[i-1]+fib[i-2];
		}
		return fib;
	}
	
	public static int fibonaccisearch(int[] arr,int value) {
		int low=0;//指针low表示待查元素所在范围的下界，下界索引从0开始
		int high=arr.length-1;//指针high表示待查元素所在范围的上界
		int k=0;//表示斐波那契分割数值的下标
		int mid=0;
		int fib[]=fibonacci();//获取到斐波那契数列
		
		while(high>fib[k]-1) {//获取到斐波那契分割数值的下标
			k++;
		}
		
		int[] temp=Arrays.copyOf(arr, fib[k]);//因为f[k]值 可能大于a的 长度，因此我们需要使用Arrays.copyOf方法，构造一个新的数组，并指向temp[]
		for(int i=high+1;i<temp.length;i++) {//使用arr数组最后的数填充 temp
			temp[i]=arr[high];
		}
		
		while(low<high) {
			mid=low+fib[k-1]-1;//斐波拉契中间值公式
			if(value<temp[mid]) {//关键字值小于中间值，应该向左扫描即使high=mid-1
				high=mid-1;
				k-=1;
			}else if(value>temp[mid]) {//关键字值大于中间值，应该向右扫描即使low=mid+1
				low=mid+1;
				k-=2;
			}else {//找到时需要确定返回哪个下标
				if(mid<=high) {//证明mid索引在原数组中，返回 mid
					return mid;
				}else {//证明mid索引已经越界（相对于原数组来说），返回 high
					return high;
				}
			}
		}
		return -1;//没有找到即返回-1
	}

	public static void main(String[] args) {
		int[] arr= {1,5,6,33,55,233,455};
		Arrays.sort(arr);//采用斐波拉契查找时，数据需是有序不重复的,需要对该数组进行排序
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入查找元素：");
		int value=sc.nextInt();
		System.out.printf("查找元素 %d 的位置是 %d",value,fibonaccisearch(arr,value));
	}
}

运行结果：

请输入查找元素：
55
查找元素 55 的位置是 4