算法通关：006_1二分查找

查找一个数组里面是否存在num

主要代码

/*** @Author: ggdpzhk* @CreateTime: 2024-07-27*/
public class cg {//二分查找public static boolean exist(int[] arr,int num){if(arr == null || arr.length == 0){return false;}int l = 0;int r = arr.length -1;while(l <= r){int m = l + ((r-l)>>2);if(num == arr[m]){return true;}else if (arr[m] < num){l = m + 1;}else{r = m - 1;}}return true;}public static void main(String[] args) {int[] arr = {1,2,3,4,5,6,7,8,9};int num = 10;if(exist(arr,num)){System.out.println("数组中存在"+num);}else{System.out.println("数组中不存在"+num);}}
}

运行结果

详细写法

自动生成数组和num，利用对数器查看二分代码是否正确

import java.util.Arrays;/*** @Author: ggdpzhk* @CreateTime: 2024-07-23*/
public class _006 {//二分查找//保证数组有序才能用二分查找，不然无意义public static boolean exist(int[] arr,int num){if(arr == null || arr.length == 0){return false;}//最开始左右边界的搜索范围int l = 0;int r = arr.length-1;int m ;//表示中点坐标的变量while(l <= r){/*m = (l+r)/2;m = l + (r-l)/2;m = l + ((r-l) >> 1);上述两种写法都可以，但是第二种更好。第三行等同于第二行    右移一位就等于除以2防止溢出就是l+r可能会溢出（数字很大），在除以2 就会出问题但是先求差，加数较小*/m = l + (r-l)/2;if(arr[m] == num){return true;}else if(arr[m] > num){/*num：我们要找的数字中间值大于num，说明num如果存在，必在 中间值的左边所以查询范围修改左边 arr[0]   右边到 中间值的前一个，也就是arr[m-1]*/r = m - 1;}else {l = m + 1;}}//每次这种我都不知道 什么条件应该返回true或者false。//但是满足上面的情况我们就返回true，剩下的不管会出现什么情况 我们都返回false//这里面有程序员的思路，多练习，加油return false;}//为了验证//对数器//为了保证你上面的方法是正确的public static boolean right(int[] arr,int num){/*if(arr == null || arr.length == 0){return false;长度检查是无用的，不可能为null或者长度为0这些限制条件在 自己写的方法随机生成数组中已经考虑到了}*///暴力解//从数组第一个数字开始，一个一个对比，如果一样就返回true。后面代码不再执行//如果查找完整个数组都没有找到num，就返回truefor(int i : arr){if(i == num ){return true;}}return false;}//为了验证//方法：循环 随机生成数字放入数组元素public static int[] randomArray(int n,int V){//写一个循环 随机生成数字放入数组元素int[] arr = new int[n];for(int i = 0;i < arr.length;i++){arr[i] = (int)(Math.random()*V)+1; //1~V}return arr;}//为了验证//随机生成满足的数组，用于测试用例public static void main(String[] args) {//   这里都是对数器的测试，如果测试通过，那我们应该写具体的输出语句，显示测试的数组和 num，以便更好地理解测试过程。/*int N = 5;//数组元素个数int V = 100;//数组最大值int testTimes = 20;//测试次数System.out.println("测试开始");for(int i = 0;i < testTimes;i++) {int n = (int) (Math.random() * N + 1);//1~N//调用方法 生成测试数组用例int[] arr = randomArray(n, V);Arrays.sort(arr);//Arrays包自带的方法，将数组从小到大排序。// 或者你用冒泡选择插入排序三种自己写的方法都行，但是人家有自带的方法为什么不用int num = (int) (Math.random() * V);// [0,V)--------选定num，看数组里有没有这个数// 这里的N写啥都行吧，就是随机生成一个数，目前对num没有条件限制//有了num，有了数组，接下来是不是就直接调方法，查找数组中有没有numif (exist(arr, num) != right(arr, num)) {System.out.println("出错了");}}System.out.println("测试结束");*/int n = 10;//几个元素int v = 20;//元素范围int[] arr = randomArray(n,v);System.out.println("数组是："+Arrays.toString(arr));int num = (int)(Math.random()*20)+1;//随机数字System.out.println("数字是"+num);//我要的是明显的结果if(exist(arr,num) == true){System.out.println("数组中存在"+num);}else{System.out.println("数组中不存在"+num);}}
}