斐波那契查找出现的问题及解决方法

先看看斐波那契查找方法斐波那契数列 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 high1; 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查找最后一个数据时就会出错。