个人电脑做外网网站,石家庄栾城区建设局网站,世界杯网络竞猜,太原网站建设vhuashi斐波那契查找原理#xff0c;仅仅改变了中间结点(mid)的位置#xff0c;mid不再是中间或插值得到,而是位于黄金分割点附近#xff0c;即midlowF(k-1)-1(F代表斐波那契数列) F[k]F[k-1]F[k-2],(F[k]-1) (F[k-1]-1)(F[k-2]-1)1 说明:只要顺序表的长度为F[k]-1,则可以将该… 斐波那契查找原理仅仅改变了中间结点(mid)的位置mid不再是中间或插值得到,而是位于黄金分割点附近即midlowF(k-1)-1(F代表斐波那契数列) 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 lowF(k-1)-1 package day7_11;import java.util.Arrays;public class Test {public static int maxSize 20;public static void main(String[] args) {int[] arr {1,8,10,89,1000,1234};int i fibSearch(arr, 1234);System.out.println(i);}public static int[]fib(){int[] f new int[maxSize];f[0] 1;f[1] 1;for(int i2;imaxSize;i){f[i] f[i-1] f[i-2];}return f;}//使用非递归的方式/**** param a 数组* param key 我们需要查找的关键码(值)* return 返回对应的下标如果没有-1*/public static int fibSearch(int[] a,int key){int low 0;int high a.length-1;int k 0;int mid 0;int f[] fib();while (high f[k] -1 ){k;}//因为f[k]值可能大于a的长度因此我们需要使用Arrays类构造一个新的数组并指向a[]//不足的部分会使用0填充int[] temp Arrays.copyOf(a,f[k]);//实际上需求使用a数组最后的数填充temp//temp {1,8,10,89,1000,1234,0,0,0} {1810,89,1000,1234,1234,1234,1234}for(int ihigh1;itemp.length;i){temp[i] a[high];}//使用while来循环处理找到我们的数keywhile (lowhigh){mid lowf[k-1]-1;if(keytemp[mid]){ //我们应该继续向数组的前面查找high mid - 1;//为什么是k-1//说明//1.全部元素 前面的元素 后边的元素//2.f[k] f[k-1] f[k-2]//因为前面有f[k-1]个元素所以可以继续拆分f[k-1] f[k-2] f[k-3]//即在f[k-1]的前面继续查找k--//即下次循环mid f[k-1-1]-1k--;}else if(keytemp[mid]){low mid 1;//为什么是k-2//说明//1.全部元素 前面的元素后边元素//2.f[k] f[k-1] f[k-2]//3.因为后面我们有f[k-2]所以可以继续拆分f[k-1] f[k-3] f[k-4]//4.即在f[k-2]的前面进行查找k-2//5.即下次循环mid f[k-1-2]-1k -2;}else{ //找到//需要确定返回的是哪个下标if(midhigh){return mid;}else{return high;}}}return -1;}}
