自己怎么做logo,免费关键词优化工具,建设工程是指哪些内容,二维码网站建设源码目录 一. 二分查找#xff08;递归#xff09;#xff1a;
代码详解#xff1a;
运行结果#xff1a;
二分查找优化#xff1a;
优化代码#xff1a;
运行结果#xff08;返回对应查找数字的下标集合#xff09;#xff1a; 编辑 二分查找#xff08;非递归…目录 一. 二分查找递归
代码详解
运行结果
二分查找优化
优化代码
运行结果返回对应查找数字的下标集合 编辑 二分查找非递归
二. 插值查找 代码详解
运行结果 三. 斐波那契[黄金分割查找]
代码详解 运行结果 一. 二分查找递归
前提条件 所要查找的数组必须为有序如果不是有序要事先排序好 二分查找思路 1. 首先确定该数组的中间的下标 mid (left right) / 2 2. 然后让需要查找的数 findVal 和 arr[mid] 比较---分情况进行讨论 2.1 findVal arr[mid] , 说明你要查找的数在mid 的右边, 因此需要递归的向右查找 2.2 findVal arr[mid], 说明你要查找的数在mid 的左边, 因此需要递归的向左查找 2.3 findVal arr[mid] 说明找到就返回 //什么时候我们需要结束递归. 1) 找到就结束递归 2) 递归完整个数组仍然没有找到findVal 也需要结束递归 当 left right 就需要退出 代码详解
public class BinarySearch {// 二分查找算法/**** param arr* 数组* param left* 左边的索引* param right* 右边的索引* param findVal* 要查找的值* return 如果找到就返回下标如果没有找到就返回 -1*/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 void main(String[] args){Scanner sc new Scanner(System.in);int[] arr new int[]{5,13,17,24,35};System.out.print(请输入要查找的数字);int n sc.nextInt();int index binarySearch(arr,0,arr.length-1,n);//一定要为有序数组if(index 0){System.out.println(找到了他的下标是index);}else{System.out.println(找不到);}}
}
运行结果
输入所要查找的数字就能返回对应的数组下标 二分查找优化 如果数组中出现多个相同的数字那我们如何得到所有要查找数字的下标呢很显然上述代码不足以解决这个问题
例如数组{1,8, 10, 89, 1000, 10001234} 这时我们需要借助集合ArrayList来解决相对简便 思路 * 1. 在找到mid 索引值不要马上返回 * 2. 向mid 索引值的左边扫描将所有满足 1000 的元素的下标加入到集合ArrayList * 3. 向mid 索引值的右边扫描将所有满足 1000 的元素的下标加入到集合ArrayList * 4. 将Arraylist返回 优化代码
public class BinarySearch {// 二分查找算法/**** param arr* 数组* param left* 左边的索引* param right* 右边的索引* param findVal* 要查找的值* return 如果找到就返回下标如果没有找到就返回 -1*/public static ListInteger binarySearch2(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 binarySearch2(arr, mid 1, right, findVal);} else if (findVal midVal) { // 向左递归return binarySearch2(arr, left, mid - 1, findVal);} else {ListInteger resIndexlist new ArrayListInteger();//向mid 索引值的左边扫描将所有满足 1000 的元素的下标加入到集合ArrayListint temp mid - 1;while(true) {if (temp 0 || arr[temp] ! findVal) {//退出break;}//否则就temp 放入到 resIndexlistresIndexlist.add(temp);temp - 1; //temp左移}resIndexlist.add(mid); ////向mid 索引值的右边扫描将所有满足 1000 的元素的下标加入到集合ArrayListtemp mid 1;while(true) {if (temp arr.length - 1 || arr[temp] ! findVal) {//退出break;}//否则就temp 放入到 resIndexlistresIndexlist.add(temp);temp 1; //temp右移}return resIndexlist;}}public static void main(String[] args){Scanner sc new Scanner(System.in);int[] arr new int[]{1,8, 10, 89, 1000, 1000,1000,1234};System.out.print(请输入要查找的数字);int n sc.nextInt();//一定要为有序数组ListInteger resIndexList binarySearch2(arr, 0, arr.length - 1, n);System.out.println(resIndexList resIndexList);}
}运行结果返回对应查找数字的下标集合 二分查找非递归
与上面类似不再过多说明直接上代码
import java.util.*;public class BinarySearch {public static int binarySearch(int[] arr,int findVal){int left 0;int right arr.length-1;while(left right){int mid (left right) / 2;if(arr[mid] findVal){return mid;}else if(arr[mid] findVal){right mid - 1;}else{left mid 1;}}return -1;//如果上述条件都没满足说明没有找到}public static void main(String[] args){Scanner sc new Scanner(System.in);int[] arr new int[]{4,8,13,78,90};System.out.print(请输入要查找的数字);int n sc.nextInt();int ret binarySearch(arr,n);if(ret 0){System.out.println(找到了它的下标是ret);}else{System.out.println(没有找到);}}
} 运行结果 二. 插值查找 举个栗子 数组 arr [1, 2, 3, ......., 100] 假如我们需要查找的值 1 使用二分查找的话我们需要多次递归才能找到 1 使用插值查找算法 int mid left (right – left) * (findVal – arr[left]) / (arr[right] – arr[left]) -----》相当于公式 int mid 0 (99 - 0) * (1 - 1)/ (100 - 1) 0 99 * 0 / 99 0 比如我们查找的值 100 int mid 0 (99 - 0) * (100 - 1) / (100 - 1) 0 99 * 99 / 99 0 99 99 相对二分查找插值查找效率更高但是与二分查找一样需要数组有序 代码详解
import java.util.*;
public class InsertValueSearch {//说明插值查找算法也要求数组是有序的/**** param arr 数组* param left 左边索引* param right 右边索引* param findVal 查找值* return 如果找到就返回对应的下标如果没有找到返回-1*/public static int insertValueSearch(int[] arr, int left, int right, int findVal) {int count 0;System.out.println(插值查找次数:(count));//注意findVal arr[0] 和 findVal arr[arr.length - 1] 必须需要//否则我们得到的 mid 可能越界if (left right || findVal arr[0] || findVal arr[arr.length - 1]) {return -1;}// 求出mid, 自适应int mid left (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);int midVal arr[mid];if (findVal midVal) { // 说明应该向右边递归return insertValueSearch(arr, mid 1, right, findVal);} else if (findVal midVal) { // 说明向左递归查找return insertValueSearch(arr, left, mid - 1, findVal);} else {return mid;}}public static void main(String[] args){Scanner sc new Scanner(System.in);System.out.print(请输入要查找的数字);int n sc.nextInt();int[] arr new int [100];for(int i 0;i 100;i){arr[i] i 1;}int ret insertValueSearch(arr,0,arr.length-1,n);if(ret 0){System.out.println(找到了它的下标是ret);}else{System.out.println(没找到);}}}运行结果 三. 斐波那契[黄金分割查找] 代码详解
import java.util.*;
public class FibonacciSearch {public static int maxSize 20;public static void main(String[] args) {Scanner sc new Scanner(System.in);System.out.print(请输入要查找的数字);int n sc.nextInt();int [] arr {1,8, 10, 89, 1000, 1234};System.out.println(index fibSearch(arr, n));// 0}//因为后面我们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;}//使用非递归的方式编写算法/**** 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; //存放mid值int f[] fib(); //获取到斐波那契数列//获取到斐波那契分割数值的下标while(high f[k] - 1) {k;}//因为 f[k] 值 可能大于 a 的 长度因此我们需要使用Arrays类构造一个新的数组并指向temp[]//不足的部分会使用0填充int[] temp Arrays.copyOf(a, f[k]);//实际上需求使用a数组最后的数填充 temp//举例://temp {1,8, 10, 89, 1000, 1234, 0, 0} {1,8, 10, 89, 1000, 1234, 1234, 1234,}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;//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 ( key temp[mid]) { // 我们应该继续向数组的后面查找(右边)low mid 1;//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(mid high) {return mid;} else {return high;}}}return -1;}
}运行结果 博客到这里也是结束了制作不易喜欢的小伙伴可以点赞加关注支持下博主这对我真的很重要~~
