顶尖网站建设公司,大余县网站,免费推广软件流量精灵,wordpress 响应式 企业网站顺序#xff08;线性#xff09;查找二分查找/折半查找插值查找斐波那契查找
线性查找 判断数列是否包含要求#xff0c;如果找到了#xff0c;就提示找到了#xff0c;并给出下标值 // 线性查找
public static ArrayListInteger seqSearch(int[] arr, int value…顺序线性查找二分查找/折半查找插值查找斐波那契查找
线性查找 判断数列是否包含要求如果找到了就提示找到了并给出下标值 // 线性查找
public static ArrayListInteger seqSearch(int[] arr, int value) {ArrayListInteger list new ArrayList();for (int i 0; i arr.length; i) {if (value arr[i]) {list.add(i);}}return list;
}二分查找
需要对一个有序数组进行二分查找 {1, 8, 10, 89, 1000, 1234}输入一个数 看看该数组是否存在此数并且求出下标如果没有就提示”没有这个数”。
思路 确定该数组的中间的下标 可以向下取整也可以向上取整。e.g:4.5向上取整为 5;向下去整为4此处演示为向下取整mid(leftright)/2 让需要查找的数findVal和arr[mid]比较 findValarr[mid说明你要查找的数在mid的右边因此需要递归的向右查找findValarr[mid]说明你要查找的数在mid的左边因此需要递归的向左查找findValarr[mid说明找到就返回 递归结束 找到就结束递归递归完整个数组仍然没有找到findVal,也需要结束递归当Ieftright就需要退出
/**
* 二分查找 ---要求数组为有序数组
* param arr 需要查询的数组
* param left 数组的最左侧下标
* param right 数组的最右侧下标
* param findVal 需要查询的值
* return
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {// 当 left right 时整个数组遍历后并未找到值if (left right) {return -1;}int mid (left right) / 2;int midVal arr[mid];if (findVal midVal) {// 右递归return binarySearch(arr, mid 1, right, findVal);} else if (findVal midVal) { // 向左递归return binarySearch(arr, left, mid - 1, findVal);} else {return mid;}
}二分优化—多索引返回
// 二分查找 ---要求数组为有序数组
public static ArrayListInteger binarySearch(int[] arr, int left, int right, int findVal) {// 当 left right 时整个数组遍历后并未找到值if (left right) {return new ArrayListInteger();}int mid (left right) / 2;int midVal arr[mid];if (findVal midVal) {// 右递归return binarySearch(arr, mid 1, right, findVal);} else if (findVal midVal) { // 向左递归return binarySearch(arr, left, mid - 1, findVal);} else {// 找到值ArrayListInteger resIndexList new ArrayList();// 向 mid 的左右两边扫描
// int temp mid - 1;
// while (true) {// 向左
// if (temp 0 || arr[temp] ! findVal) {// 退出
// break;
// }
// // 否则就temp 放入到resIndexList
// resIndexList.add(temp);
// temp - 1; // temp左移
// }
// resIndexList.add(mid); // 将中间索引加入
//
// temp mid 1;
// while (true) {// 向右
// if (temp arr.length - 1 || arr[temp] ! findVal) {// 退出
// break;
// }
// // 否则就temp 放入到resIndexList
// resIndexList.add(temp);
// temp 1; // temp右移
// }// 再优化resIndexList.add(mid); // 将中间索引加入for (int i mid - 1; i 0; i--) {// 向左if (arr[i] ! findVal) {break;}resIndexList.add(i);}for (int i mid 1; i arr.length - 1; i) {// 向右if (arr[i] ! findVal) {break;}resIndexList.add(i);}return resIndexList;}
}插值查找 需要数组是有序效率比二分查找更高效 插值查找算法类似于二分查找不同的是插值查找每次从自适应mid处开始查找。 将折半查找中的求mid索引的公式low表示左边索引high表示右边索引right m i d l o w h i g h 2 l o w 1 2 ( h i g h − l o w ) mid\frac{lowhigh}{2}low\frac{1}{2}(high-low) mid2lowhighlow21(high−low) ➡️ m i d l o w k e y − a [ l o w ] a [ h i g h ] − a [ l o w ] ( h i g h − l o w ) midlow\frac{key-a[low]}{a[high]-a[low]}(high-low) midlowa[high]−a[low]key−a[low](high−low) 【其中key为需要查找的值】 公式优化int m i d I n d e x l o w ( h i g h − l o w ) ∗ ( k e y − a r r [ l o w ] ) / ( a r r [ h i g h ] − a r r [ l o w ] ) ; midIndexlow(high-low)*(key-arr[low])/(arr[high]-arr[low]); midIndexlow(high−low)∗(key−arr[low])/(arr[high]−arr[low]);
// 插值查找 ---要求数组为有序数组
// 其中key为需要查找的值
public static int insertValueSearch(int[] arr, int left, int right, int key) {// 注意key arr[0] || key arr[arr.length - 1]必须要有优化作用否则可能会造成midIndex越界if (left right || key arr[0] || key arr[arr.length - 1]) {return -1;}int midIndex left (right - left) * (key - arr[left]) / (arr[right] - arr[left]);int midVal arr[midIndex];if (key midVal) {// 向右扫描递归return insertValueSearch(arr, midIndex 1, right, key);} else if (key midVal) {// 向左扫描递归return insertValueSearch(arr, left, midIndex - 1, key);} else {return midIndex;}}总结
对于数据量较大关键字分布比较均匀的查找表来说采用插值查找速度较快关键字分布不均匀的情况下该方法不一定比折半查找要好 斐波那契查找黄金分割法 需要数组是有序 黄金分割点是指把一条线段分割为两部分使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽因此称为黄金分割也称为中外比。这是一个神奇的数字会带来意向不大的效果。斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例无限接近黄金分割值0.618
原理 斐波那契查找原理与前两种相似仅仅改变了中间结点(mid)的位置mid不再是中间或插值得到而是位于黄金分割点附近即 m i d l o w F ( k − 1 ) − 1 midlowF(k-1)-1 midlowF(k−1)−1 (F代表斐波那契数列。k代表斐波那契个数)
对F(k-1)-1的理解 由斐波那契数列 F [ K ] F [ k − 1 ] F [ k − 2 ] F[K]F[k-1]F[k-2] 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)1 (F[k]−1)(F[k−1]−1)(F[k−2]−1)1 该式说明只要顺序表的长度为 F [ k ] − 1 F[k]-1 F[k]−1则可以将该表分成长度为 F [ k − 1 ] − 1 F[k-1]-1 F[k−1]−1和 F [ k − 2 ] − 1 F[k-2]-1 F[k−2]−1的两段从而中间位置为 m i d l o w F ( k − 1 ) − 1 midlowF(k-1)-1 midlowF(k−1)−1 类似的每一子段也可以用相同的方式分割 但顺序表长度 n n n不一定刚好等于 F [ K ] − 1 F[K]-1 F[K]−1所以需要将原来的顺序表长度n增加至 F [ K ] − 1 F[K]-1 F[K]−1。这里的 k k k值只要能使得 F [ k ] − 1 F[k]-1 F[k]−1恰好大于或等于 n n n即可由以下代码得到顺序表长度增加后新增的位置从 n 1 n1 n1到 F [ K ] − 1 F[K]-1 F[K]−1位置)都赋为 n n n位置的值即可。 while (high f[k] - 1) {// 如果大于则kk;
}注意因为黄金分割点是第三段的前一段除以整段之所以减1是因为数组是从0开始所以 F [ k ] − 1 ( F [ k − 1 ] − 1 ) ( F [ k − 2 ] − 1 ) 分割点 F[k]-1(F[k-1]-1)(F[k-2]-1)分割点 F[k]−1(F[k−1]−1)(F[k−2]−1)分割点第三点由于f(k) 有可能小于n也就是high就不满足斐波那契数列要求
// 使用非递归方法得到一个斐波那契数列
public static int maxSize 20;// 后面需要midlowF(k-1)-1因此先获取一个斐波那契数列
public static int[] fib() {int[] f new int[maxSize];f[0] 1;f[1] 1;for (int i 2; i maxSize; i) {f[i] f[i - 1] f[i - 2];}return f;
}// 斐波那契查找 --- 非递归
// key为需要查找的关键码(值)
public static int fibSearch(int[] a, int key) {int low 0;int high a.length - 1;int k 0; // 表示斐波那契分割数值的下标int mid 0; // 存放a数组分割点int[] f fib(); // 获取到斐波那契数列// 获取到斐波那契分割数值的下标// f[k] - 1 为临时数组的长度不得小于a数组的长度while (high f[k] - 1) {// 如果大于则kk;}// f[k] 可能大于a 的长度因此需要使用Arrays类构造一个新的数组并指向temp[]// 不足的部分会使用0填充int[] temp Arrays.copyOf(a, f[k]);// 实际上需要使用a数组的数填充temp// temp {1, 8, 10, 80, 1000, 0, 0, 0} {1, 8, 10, 80, 1000, 1000, 1000, 1000}for (int i high 1; i temp.length; i) {temp[i] a[high];}// 使用while 来循环处理找到我们的数keywhile (low high) {mid low f[k - 1] - 1;if (key temp[mid]) {// 向左边查找high mid - 1;// f[k] f[k-1] f[k-2]之后f[k-1]继续拆分因此k--k--;} else if (key temp[mid]) { // 向右查找low mid 1;// f[k] f[k-1] f[k-2]之后f[k-2]继续拆分// f[k-1] f[k-3] f[k-4]因此k -2k - 2;} else {// 找到if (mid high) {return mid;} else {return high;}}}return -1;
}
