图解斐波那契搜索并使用java实现

斐波那契查找是在二分查找之上进行了优化
将查找系数0.5换成了接近黄金分割比的系数
假设有一个裴波那契数组int[] F和一个要进行搜索的数组int[] arr;
arr.length = F[F.length -1]
即数组的长度等于裴波那契数组最后一个值
在契数列中任意一个值F[k] F[k - 2]/F[k - 1]近似于于黄金分割比
即数字F[k] 的近似黄金分割点为 F[k - 1]
将二分查找的中间系数改为
int middle = left + F[k - 1] -1 ; //因为数组从0开始所以要减去1

public static int fibonacciSearch(int[] arr,int target) {
		int[] F = Fibonacci(arr.length);
		int[] temp = new int[F[F.length - 1]];
		for (int i = 0; i < temp.length; i++) {
			if(i < arr.length) {
				temp[i] = arr[i];
			}else {
				temp[i] = arr[arr.length -1];
			}
			
		}
		int left = 0;
		int right = temp.length -1;
		int k = F.length - 1;
		int middle =left + F[k - 1] -1;
		while(left <= right && k > 1) {
			middle = left + F[k - 1] - 1;
			if(temp[middle] == target) {
				return middle;
			}else if(temp[middle] > target) {
				right = middle -1;
				k --;
			}else if(temp[middle] < target) {
				k -= 2;
				left = middle + 1;
			}
		}
		return -1;
	}
	//生成一个裴波那契数列，最后一个值大于指定的值，倒数第二个值小于指定的值
	public static int[] Fibonacci(int length) {
		int count = 2;
		int i = 1;
		int j = 1;
		int x = 0;
		while (x < length) {
			x = i + j;
			i = j;
			j = x;
			count ++;
		}
		int[] F = new int[count];
		F[0] = 1;
		F[1] = 1;
		for (int k = 2; k < F.length; k++) {
			F[k] = F[k - 1] + F[k - 2];
		}
		return F;
	}