斐波拉契查找法的原理及实现
斐波拉契查找法与二分法和插值查找法大致类似，后两者在寻找mid值的过程中都用到了除法，特别是在插值查找法中寻找mid值同时用到了乘除法，与加减法相比，乘除法无疑更消耗时间，因此，斐波拉契查找法利用斐波拉契数列去寻找mid值，整个过程巧妙的避开了使用乘除法，是一种空间换时间的方法。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
如上所示，斐波拉契数列的一个特点就是从第2(0为第一个数)个数开始，每一个数都是前面两个数的和(这刚好满足了二分查找中，我们想把数据分为左右两部分的需求)。
一个斐波拉契数组，数组名fibonacciArr，则满足:
fibonacciArr[n] = fibonacciArr[n-1] + fibonacciArr[n-2] (n>=2) ;
因此我们可以将待查找的数组arr的长度arr.length扩展到斐波拉契数组中的一个合适的值fibonacciArr[k] (k 满足：fibonacciArr[k] >=arr.length && fibonacciArr[k-1] <arr.length) 。这样在二分数组时，就可以根据斐波拉契数列里的查到的值去二分(这里就是空间换时间)。比如现在arr的长度被扩展到了fibonacciArr[k]的大小，扩展后的数组记为arr1，我们斐波拉契数组里查询到 fibonacciArr[k-1] 及 fibonacciArr[k-2] 的值，就可以将arr1分为左段( 长度为:fibonacciArr[k-1] )和右段( 长度为:fibonacciArr[k-2] )。
以上就是斐波拉契查找法的思想。
由fibonacciArr[n] = fibonacciArr[n-1] + fibonacciArr[n-2] 可以得到：
fibonacciArr[n] - 1 = fibonacciArr[n-1] - 1 + fibonacciArr[n-2] - 1 + 1
即把斐波拉契数组里面的每个数都减1，那么就能空出一个位置留给mid
如上图所示，为了便于代码实现，将扩展后的数组arr1根据斐波拉契数组分成了三个部分，然后采用递归的方法(for循环一样)就能实现斐波拉契查找法。
java代码实现：
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
/**
* 斐波那契查找
*
* 由于在计算mid时使用的是斐波拉契数列，所以没有用到除法。整个查找过程只用到了加减法
* 相比于二分法，没有乘法和除法，所以统计上说会更快
* @author MSI
*
*/
public class FibonacciSearch {
public static void main(String[] args) {
int[] arr = {0,1,2,2,2,5,6,7,7,7,7};
System.out.println(fibonacciSort(arr,7));
}
/**
* 产生斐波那契数列
*
* @param maxSize 需要的最大长度
* @return
*/
public static int[] fibonacciArray(int maxSize) {
int[] arr = new int[maxSize];
arr[0] = arr[1] = 1;
for (int i = 2; i < arr.length; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr;
}
/**
* 在这里面调用递归函数
* @param arr
* @param num
* @return
*/
public static List<Integer> fibonacciSort(int[] arr, int num) {
//现在斐波那契数列中找到一个最接近于且大于arr长度的斐波那契数
int[] fibArr = fibonacciArray(20); //这里的20应该是根据数组的长度动态变化的
int k = 0;
//F(n)-1 = F(n-1)-1 + F(n-2)-1 + 1
//左段：left ~ left + F(n-1) - 2
//中间值： left + F(n-1) - 1
//右段：left + F(n-1) ~ right
for (int i = 2; i < fibArr.length; i++) { //斐波那契数列前两个都是1，直接从非1的数开始寻找
if(fibArr[i] - 1 >= arr.length && fibArr[i - 1] - 1 < arr.length) {
k = i;
break;
}
}
//将原数组填充到相应斐波那契数的大小
int[] arr1 = Arrays.copyOf(arr, fibArr[k] - 1);
for(int j = arr.length; j < arr1.length; j++) {
arr1[j] = arr[arr.length - 1];
}
//调用递归函数
return recursionFuc(arr1, fibArr, arr.length, k, 0, arr1.length - 1, num);
}
/**
* 递归函数
* @param arr1 补充后的数组
* @param fiboarr 斐波拉契数组
* @param arrLen 原数组长度
* @param k 索引到斐波那契数组第几个值了
* @param left 该段左边界限
* @param right 该段右边界限
* @param num 要找的值
* @return
*/
public static List<Integer> recursionFuc(int[] arr1, int[] fiboarr, int arrLen, int k, int left, int right, int num) {
//F(n)-1 = F(n-1)-1 + F(n-2)-1 + 1
//left:
if(left > right) {
return new ArrayList<Integer>();
}
int mid = left + fiboarr[k-1] - 1; //中间位置
if(num == arr1[mid] && mid < arrLen) {
List<Integer> list = new ArrayList<Integer>();
list.add(mid);
int mid_l = mid-1;
int mid_r = mid+1;
while(mid_l >= 0 && arr1[mid_l] == num) { //向左查找，是否还存在目标数据
list.add(mid_l);
mid_l--;
}
while(mid_r < arrLen && arr1[mid_r] == num) { //向右查找，是否还存在目标数据
list.add(mid_r);
mid_r++;
}
return list;
}else if (num > arr1[mid]) { //右
return recursionFuc(arr1,fiboarr, arrLen, k-2, mid + 1,right, num);
}else{
return recursionFuc(arr1,fiboarr, arrLen, k-1, left, mid-1, num);
}
}
}
执行结果：