当前位置: 首页 > news >正文

【算法】递归实现二分查找(优化)以及非递归实现二分查找

递归实现二分查找 
思路分析

1.首先确定该数组中间的下标 mid = (left + right) / 2;

2.然后让需要查找的数 findVal 和 arr[mid] 比较

  1. findVal > arr[mid],说明要查找的数在 arr[mid] 右边,需要向右递归
  2. findVal < arr[mid],说明要查找的数在 arr[mid] 左边,需要向左递归
  3. findVal == arr[mid],说明找到,返回

什么时候结束递归

1.找到就结束递归

2.递归完整个数组,依然没有找到,即 left > right 就阶结束递归

//注意:使用二分查找的前提是该数组是有序的
public class BinarySearch {public static void main(String[] args) {int[] arr = {-3, 1, 18, 99, 1000, 1024};int findVal = 99;int index = binarySearch(arr, 0, arr.length - 1, findVal);System.out.printf("%d的索引为%d\n", findVal, index);}//二分查找算法public static int binarySearch(int[] arr, int left, int right, int findVal) {//如果找不到,返回 -1if (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;}}
}
优化

当一个有序数组中有多个相同数值时,如{-3, 1, 18, 99,99, 1000, 1024},如何将所有数值都查找到,比如这里的 99

思路分析

1.在找到 mid 值,不要马上返回

2.向 mid 索引值的左边扫描,将所有满足的下标加入集合 ArrayList

3.向 mid 索引值的右边扫描,将所有满足的下标加入集合 ArrayList

4.将 ArrayList 返回

//注意:使用二分查找的前提是该数组是有序的
public class BinarySearch {public static void main(String[] args) {int[] arr = {-3, 1, 18, 99, 99, 99, 1000, 1024};int findVal = 99;ArrayList<Integer> resIndexList = binarySearch(arr, 0, arr.length - 1, findVal);System.out.printf("resIndexList = " + resIndexList);}//优化二分查找算法public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int findVal) {//如果找不到,返回 -1if (left > right) {return new ArrayList<Integer>();}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 {/*1.在找到 mid 值,不要马上返回2.向 mid 索引值的左边扫描,将所有满足的下标加入集合 ArrayList3.向 mid 索引值的右边扫描,将所有满足的下标加入集合 ArrayList4.将 ArrayList 返回*/ArrayList<Integer> resIndexlist = new ArrayList<>();//向左扫描int temp = mid - 1;while (true) {if (temp < 0 || arr[temp] != findVal) {  //退出break;}//否则,就将 temp 放入到 resIndexlistresIndexlist.add(temp);temp -= 1;  //temp 左移}resIndexlist.add(mid);//向右扫描temp = mid + 1;while (true) {if (temp > arr.length - 1 || arr[temp] != findVal) {  //退出break;}//否则,就将 temp 放入到 resIndexlistresIndexlist.add(temp);temp += 1;  //temp 左移}return resIndexlist;}}
}

非递归实现二分查找
public class BinarySearchNoRecursion {public static void main(String[] args) {int[] arr = {1, 2, 8, 999, 1024, 1234};int target = 8;System.out.println("待查询数组为:" + Arrays.toString(arr));System.out.printf("%d的下标索引为%d", target, binarySearch(arr, target));}/**** @param arr  待查找的数组,升序* @param target  待查找的数* @return  返回对应的下标,-1 表示没有找到*/public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {  //说明可以继续查找int mid = (left + right) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] > target) {right = mid - 1;} else {left = mid + 1;}}return -1;}
}
http://www.lryc.cn/news/414900.html

相关文章:

  • CDN 是什么?
  • 索引:SpringCloudAlibaba分布式组件全部框架笔记
  • 2024第五届华数杯数学建模竞赛C题思路+代码
  • FFmpeg源码:av_reduce函数分析
  • nginx: [error] open() “/run/nginx.pid“ failed (2: No such file or directory)
  • <数据集>BDD100K人车识别数据集<目标检测>
  • 利用SSE打造极简web聊天室
  • 代码随想录第二十天|动态规划(4)
  • TreeSize:免费的磁盘清理与管理神器,解决C盘爆满的燃眉之急
  • 如何建立自己的技术知识体系
  • JS优化了4个自定义倒计时
  • 模型实战(25)之 基于LoFTR深度学习匹配算法实现图像拼接
  • 计算机毕业设计Python+Spark知识图谱高考志愿推荐系统 高考数据分析 高考可视化 高考大数据 大数据毕业设计
  • 【python】文件
  • 《Attention Is All You Need》核心观点及概念
  • 【中项】系统集成项目管理工程师-第9章 项目管理概论-9.9价值交付系统
  • JS+H5美观的带搜索的博客文章列表(可搜索多个参数)
  • 牛客周赛 Round 54 (c++题解)
  • htsjdk库Genotype及相关类介绍
  • C++ 最短路(spfa) 洛谷
  • MySQL的数据类型
  • xss漏洞(四,xss常见类型)
  • 繁简之争:为什么手机芯片都是 ARM
  • 【nnUNetv2进阶】十九、nnUNetv2 使用ResidualEncoder训练模型
  • Unity3D ShaderGraph 场景扫描光效果实现详解
  • JS中运算符优先级
  • 分享6款有助于写论文能用到的软件app!
  • Python图形验证码的识别:一步步详解
  • Jenkins未授权访问漏洞
  • 什么情况下跑代码内存才会爆