1、二分法查找的背景
当数组或者集合中存放的元素数量非常多的时候,想要跟踪具体某个元素的位置或者是否存在,常规方式是循环每一个元素直到找到要查找的元素为止。这样的查找方式效率非常低下,这个时候需要使用二分法来实现,提高查找效率。
2、二分法查找的介绍
二分法查找(折半查找),找指定数值所在的位置
百度百科是这样介绍二分法查找的:
3、二分法查找的算法思想
假设数组是按升序排序的,对于给定的目标值aim,从数组的中间位置开始查找:1.若查找数据与中间元素值正好相等,则返回中间元素值的索引;2.若查找数值比中间值小,则以整个查找范围的前半部分作为新的查找范围;3.若查找数值比中间值大,则以整个查找范围的后半部分作为新的查找范围;注:查找成功返回索引,失败返回-1
4、代码实现
4.1 利用循环的方式实现二分法查找
- public class BinarySearch {
- public static void main(String[] args) {
- // 生成一个随机数组
- int[] array = suiji();
- // 对随机数组排序
- Arrays.sort(array);
- System.out.println("产生的随机数组为: " + Arrays.toString(array));
- System.out.println("要进行查找的值: ");
- Scanner input = new Scanner(System.in);
- // 进行查找的目标值
- int aim = input.nextInt();
- // 使用二分法查找
- int index = binarySearch(array, aim);
- System.out.println("查找的值的索引位置: " + index);
- }
- /**
- * 生成一个随机数组
- *
- * @return 返回值,返回一个随机数组
- */
- private static int[] suiji() {
- // random.nextInt(n)+m 返回m到m+n-1之间的随机数
- int n = new Random().nextInt(6) + 5;
- int[] array = new int[n];
- // 循环遍历为数组赋值
- for (int i = 0; i < array.length; i++) {
- array[i] = new Random().nextInt(100);
- }
- return array;
- }
- /**
- * 二分法查找 ---循环的方式实现
- *
- * @param array 要查找的数组
- * @param aim 要查找的值
- * @return 返回值,成功返回索引,失败返回-1
- */
- private static int binarySearch(int[] array, int aim) {
- // 数组最小索引值
- int left = 0;
- // 数组最大索引值
- int right = array.length - 1;
- int mid;
- while (left <= right) {
- mid = (left + right) / 2;
- // 若查找数值比中间值小,则以整个查找范围的前半部分作为新的查找范围
- if (aim < array[mid]) {
- right = mid - 1;
- // 若查找数值比中间值大,则以整个查找范围的后半部分作为新的查找范围
- } else if (aim > array[mid]) {
- left = mid + 1;
- // 若查找数据与中间元素值正好相等,则放回中间元素值的索引
- } else {
- return mid;
- }
- }
- return -1;
- }
- }
代码执行结果:
- 产生的随机数组为: [16, 33, 40, 46, 57, 63, 65, 71, 85]
- 要进行查找的值:
- 46
- 查找的值的索引位置: 3
若输入的值找不到,则返回-1
- 产生的随机数组为: [28, 41, 47, 56, 70, 81, 85, 88, 95]
- 要进行查找的值:
- 66
- 查找的值的索引位置: -1
4.2 利用递归的方式实现二分法查找
- public class BinarySearch2 {
- public static void main(String[] args) {
- // 生成一个随机数组
- int[] array = suiji();
- // 对随机数组排序
- Arrays.sort(array);
- System.out.println("产生的随机数组为: " + Arrays.toString(array));
- System.out.println("要进行查找的值: ");
- Scanner input = new Scanner(System.in);
- // 进行查找的目标值
- int aim = input.nextInt();
- // 使用二分法查找
- int index = binarySearch(array, aim, 0, array.length - 1);
- System.out.println("查找的值的索引位置: " + index);
- }
- /**
- * 生成一个随机数组
- *
- * @return 返回值,返回一个随机数组
- */
- private static int[] suiji() {
- // Random.nextInt(n)+m 返回m到m+n-1之间的随机数
- int n = new Random().nextInt(6) + 5;
- int[] array = new int[n];
- // 循环遍历为数组赋值
- for (int i = 0; i < array.length; i++) {
- array[i] = new Random().nextInt(100);
- }
- return array;
- }
- /**
- * 二分法查找 ---递归的方式
- *
- * @param array 要查找的数组
- * @param aim 要查找的值
- * @param left 左边最小值
- * @param right 右边最大值
- * @return 返回值,成功返回索引,失败返回-1
- */
- private static int binarySearch(int[] array, int aim, int left, int right) {
- if (aim < array[left] || aim > array[right]) {
- return -1;
- }
- // 找中间值
- int mid = (left + right) / 2;
- if (array[mid] == aim) {
- return mid;
- } else if (array[mid] > aim) {
- //如果中间值大于要找的值则从左边一半继续递归
- return binarySearch(array, aim, left, mid - 1);
- } else {
- //如果中间值小于要找的值则从右边一半继续递归
- return binarySearch(array, aim, mid + 1, array.length-1);
- }
- }
- }
递归相较于循环,代码比较简洁,但是时间和空间消耗比较大,效率低。在实际的学习与工作中,根据情况选择使用。
12月20日,在2020 Techo Park开发者大会云开发分论坛上,腾讯云发布了云开发的最...
如何启动程序 双击(windows系统下),或者在shell终端上执行./a.out 在shell终端...
直达最佳实践:【 SAP(HANA+S/4)上云基础环境部署最佳实践 】 最佳实践频道:...
服务器按机箱结构划分可分为4类:台式服务器、机架式服务器、机柜式服务器和刀片...
什么 云主机 免费试用?虽然国内有很多的厂商都提供 云服务器 试用,有的是免费...
一、本地使用nacos1. 下载nacos安装包 2.0.1是最新版 1.4.2是稳定版 2. 启动naco...
Step 1:创建 Notebook 实例 1.登录 智能钛机器学习平台控制台 ,单击菜单栏的【...
背景 前段时间在我的技术群里,大家讨论起了为什么UserMapper.java是个接口,没...
瞻博网络MX系列路由器提供分段路由流量工程全功能支持,具备强大的遥测能力,帮助...
本文介绍在云桌面上安装应用程序的方法。 如果您需要在云桌面上安装新的应用程序...