21.二分查找算法
2022/1/16 22:04:10
本文主要是介绍21.二分查找算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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; } }
2.课后思考题: {1,8, 10, 89, 1000, 1000,1234} 当一个有序数组中, 有多个相同的数值时,如何将所有的数值都查找到,比如这里的 1000
public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) { System.out.println("hello~"); // 当 left > right 时,说明递归整个数组,但是没有找到 if (left > right) { return new ArrayList<Integer>(); } 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 { // * 思路分析 // * 1. 在找到mid 索引值,不要马上返回 // * 2. 向mid 索引值的左边扫描,将所有满足 1000, 的元素的下标,加入到集合ArrayList // * 3. 向mid 索引值的右边扫描,将所有满足 1000, 的元素的下标,加入到集合ArrayList // * 4. 将Arraylist返回 List<Integer> resIndexlist = new ArrayList<Integer>(); //向mid 索引值的左边扫描,将所有满足 1000, 的元素的下标,加入到集合ArrayList int temp = mid - 1; //退出 while (temp >= 0 && arr[temp] == findVal) { //否则,就temp 放入到 resIndexlist resIndexlist.add(temp); temp -= 1; //temp左移 } resIndexlist.add(mid); // //向mid 索引值的右边扫描,将所有满足 1000, 的元素的下标,加入到集合ArrayList temp = mid + 1; //退出 while (temp <= arr.length - 1 && arr[temp] == findVal) { //否则,就temp 放入到 resIndexlist resIndexlist.add(temp); temp += 1; //temp右移 } return resIndexlist; } }
这篇关于21.二分查找算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南