企业官网建设流程全解析

先看看斐波那契查找方法

斐波那契数列 1 1 2 3 5 8 13 21 …
斐波那契数列 的前一项f[k-1]/f[k] 随着k越来越大，这个值逐渐趋近黄金分割点0.618

如果查找的数据长度等于斐波那契数列的某一项数。则可以直接进行查找，否则 就需要将查找目标数组进行扩列，扩列数用目标数组高位填充

假设目标数组 1,2,3,4,5,6 数据长度为6 那么就需要进行扩列到8 即 1,2,3,4,5,6,7,8
由于f[k] = f[k-1]+f[k-2] 8 = 3 +5 则查找就分为前5后3，以此类推***

import java.lang.reflect.Array; import java.util.Arrays; /** * 斐波那契查找 */ public class FibnqSearch { /** * 采用非递归的方式 * @param arr * @param key 查找的值 * @return */ public static int serach(int[] arr,int key){ int low = 0; int high = arr.length - 1; int k = 0; //斐波那契分割数值的下标 int mid = 0; //存放mid值 int[] fibarr = new int[20]; fibarr[0] = 1; fibarr[1] = 1; for (int i = 2; i < fibarr.length; i++) { fibarr[i] = fibarr[i-1] + fibarr[i-2]; } //获取到斐波那契分割数值的下标 while (high > fibarr[k] - 1){ k++; } //不足的部分用0补齐 int[] temp = Arrays.copyOf(arr,fibarr[k]); //将temp的高位以后的数据全部填充arr高位的数据 for (int i = high+1; i <temp.length ; i++) { temp[i] = arr[high]; } //找到key值 while (low <= high){ mid = low + fibarr[k-1] - 1; //向左查找 if (key < temp[mid]){ high = mid - 1; k--; }else if (key > temp[mid]){ //向右查找 low = mid + 1; k -= 2; }else { if (mid <= high){ return mid; }else { //如果数组填充了，就返回没填充之前的最高位 return high; } } } return -1; } }

下面描述下出现的问题：当查找的数据长度为5的时候，查找最后一个数，会出现斐波那契下标越界。
查找目标数据 1,2,3,4,5 查找 5
在计算

mid = low + fibarr[k-1] - 1;

会出现异常，修改后的代码如下：

if (k > 0){ mid = low + fibarr[k-1] - 1; }else { mid = low; }

这样一来就避免了异常问题，很奇怪，唯独在数据长度为5，查找最后一个数据时就会出错。