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

(一)Java算法:二分查找

目录

    • 一、简介
      • 1.1、特点
      • 1.2、实现思路
    • 二、maven依赖
    • 三、递归方式
      • 3.1、代码实现
      • 3.2、数据流向过程
      • 3.3、数据查找流程
    • 四、游标方式
      • 4.1、代码实现
      • 4.2、数据流向过程
      • 4.3、数据查找流程
    • 结语

一、简介

1.1、特点

  二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,二分查找有两个要求:

  • 线性表必须采用顺序存储结构
  • 线性表中元素按关键字有序排列

1.2、实现思路

  二分查找查询的大致思路:每次取线性表中间位置的值与待查关键字的值进行比较:

  • 如果待查关键字的值比中间位置的值小,则在前半部分循环这个查找的过程
  • 如果待查关键字的值比中间位置的值大,则在后半部分循环这个查找的过程
  • 直到待查关键字的值和中间位置的值相等,否则线性表中没有待查的关键字

二、maven依赖

pom.xml

<dependencies>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter</artifactId>
        <version>2.6.0</version>
    </dependency>

    <dependency>
        <groupId>org.projectlombok</groupId>
        <artifactId>lombok</artifactId>
        <version>1.16.14</version>
    </dependency>
</dependencies>

  本文中springboot的版本还是2.6.0

三、递归方式

3.1、代码实现

	/**
     * 二分查找法
     *
     * @param arr    要查找的数组(必须采用顺序存储结构,而且表中元素按关键字有序排列)
     * @param startIndex  从要查找数组的哪个索引开始
     * @param endIndex    从要查找数组的哪个索引结束
     * @param targetValue 要查找的值
     * @return 如果查询到则返回该数据在数组中的索引
     * 如果未查到则返回-1
     */
    public static int binarySearch(int[] arr, int startIndex, int endIndex, int targetValue) {
        if (startIndex < 0 || endIndex >= arr.length) {
            log.info("索引值应该大于-1,并且小于数组的长度减1,此时的开始索引:{},结束索引:{}", startIndex, endIndex);
            return -1;
        }
        if (startIndex > endIndex) {
            log.info("开始索引必须大于结束索引,此时的开始索引:{},结束索引:{}", startIndex, endIndex);
            return -1;
        }
        if (targetValue < arr[startIndex]) {
            log.info("要查询的值【{}】小于数组的最小值【{}】", targetValue, arr[startIndex]);
            return -1;
        }
        if (targetValue > arr[endIndex]) {
            log.info("要查询的值【{}】大于数组的最小值【{}】", targetValue, arr[endIndex]);
            return -1;
        }
        log.info("从索引start={}到索引end={},要检索的数组范围为:{}", startIndex, endIndex, Arrays.copyOfRange(arr, startIndex, endIndex + 1));
        //获取中间值及其索引
        int midIndex = (startIndex + endIndex) / 2;
        int midValue = arr[midIndex];
        log.info("此时要检索的数组的中间值为:{},索引为:{}", midValue, midIndex);
        if (targetValue < midValue) {
            log.info("目标元素【{}】小于中间值【{}】,接下来从索引start={}到索引end={}进行检索", targetValue, midValue, startIndex, midIndex - 1);
            return binarySearch(arr, startIndex, midIndex - 1, targetValue);
        } else if (targetValue > midValue) {
            log.info("目标元素【{}】大于中间值【{}】,接下来从索引start={}到索引end={}进行检索", targetValue, midValue, midIndex + 1, endIndex);
            return binarySearch(arr, midIndex + 1, endIndex, targetValue);
        } else {
            log.info("目标元素【{}】等于中间值【{}】,找到数据,索引值为:{}", targetValue, midValue, midIndex);
            return midIndex;
        }
    }

    public static void main(String[] args) {
        //注意此数组应该是线性的,递增或者递减(本文是递增)
        //如果是递减得修改算法里的条件判断,思路一样
        int int[] arr = new int[]{3, 7, 8, 13, 14, 16, 18, 28, 30};
		//调用递归方式的二分查找法
        int i = binarySearch(arr, 0, arr.length-1, 8);
        log.info("递归方式实现二分查找法查询结果:{}", i);
    }

3.2、数据流向过程

  假设我们在数组中查找 8 ,那么查找的数据流程如下表格:(蓝色的表示要查找的范围)

数组索引012345678
原数组元素(查找8)378131416182830
第一次数组查找范围378131416182830
中间值14(8<14)----14----
第二次数组查找范围378131416182830
中间值7(8>7)-7-------
第三次数组查找范围378131416182830
中间值8(8==8)--8------
两个值相等--找到了------

3.3、数据查找流程

从索引start=0到索引end=8,要检索的数组范围为:[3, 7, 8, 13, 14, 16, 18, 28, 30]
此时要检索的数组的中间值为:14,索引为:4
目标元素【8】小于中间值【14】,接下来从索引start=0到索引end=3进行检索
从索引start=0到索引end=3,要检索的数组范围为:[3, 7, 8, 13]
此时要检索的数组的中间值为:7,索引为:1
目标元素【8】大于中间值【7】,接下来从索引start=2到索引end=3进行检索
从索引start=2到索引end=3,要检索的数组范围为:[8, 13]
此时要检索的数组的中间值为:8,索引为:2
目标元素【8】等于中间值【8】,找到数据,索引值为:2
递归方式实现二分查找法查询结果:2

四、游标方式

4.1、代码实现

	/**
     * 二分查找法
     *
     * @param arr    要查找的数组(必须采用顺序存储结构,而且表中元素按关键字有序排列)
     * @param targetValue 要查找的值
     * @return 如果查询到则返回该数据在数组中的索引
     * 如果未查到则返回-1
     */
    public static int binarySearch(int[] arr, int targetValue) {
        //定义最小索引
        int startIndex = 0;
        //定义最大索引
        int endIndex = arr.length - 1;
        //循环查找(不要越界)
        while (startIndex <= endIndex) {
            log.info("从索引start={}到索引end={},要检索的数组范围为:{}", startIndex, endIndex, Arrays.copyOfRange(arr, startIndex, endIndex + 1));
            //定义中间值的索引
            int midIndex = (startIndex + endIndex) / 2;
            //定义中间值
            int midValue = arr[midIndex];
            log.info("此时要检索的数组的中间值为:{},索引为:{}", midValue, midIndex);
            if (targetValue < midValue) {
                //要查找的值小于中间值
                endIndex = midIndex - 1;
                log.info("目标元素【{}】小于中间值【{}】,接下来从索引start={}到索引end={}进行检索", targetValue, midValue, startIndex, midIndex - 1);
            } else if (targetValue > midValue) {
                //要查找的值大于中间值
                startIndex = midIndex + 1;
                log.info("目标元素【{}】大于中间值【{}】,接下来从索引start={}到索引end={}进行检索", targetValue, midValue, midIndex + 1, endIndex);
            } else {
                //查找到要找的值
                log.info("目标元素【{}】等于中间值【{}】,找到数据,索引值为:{}", targetValue, midValue, midIndex);
                return midIndex;
            }
        }
        return -1;
    }
    
    public static void main(String[] args) {
        //注意此数组应该是线性的,递增或者递减(本文是递增)
        //如果是递减得修改算法里的条件判断,思路一样
        int int[] arr = new int[]{3, 7, 8, 13, 14, 16, 18, 28, 30};
		//调用游标方式的二分查找法
        int result = binarySearch(arr, 28);
        log.info("游标方式实现二分查找法查询结果(索引值):{}", result);
    }

4.2、数据流向过程

  假设我们在数组中查找 28 这个元素,那么查找的数据流程如下表格:(蓝色的表示要查找的范围)

数组索引012345678
原数组元素(查找8)378131416182830
第一次数组查找范围378131416182830
中间值14(28>14)----14----
第二次数组查找范围378131416182830
中间值18(28>18)------18--
第三次数组查找范围378131416182830
中间值28(28==28)-------28-
两个值相等-------找到了-

4.3、数据查找流程

从索引start=0到索引end=8,要检索的数组范围为:[3, 7, 8, 13, 14, 16, 18, 28, 30]
此时要检索的数组的中间值为:14,索引为:4
目标元素【28】大于中间值【14】,接下来从索引start=5到索引end=8进行检索
从索引start=5到索引end=8,要检索的数组范围为:[16, 18, 28, 30]
此时要检索的数组的中间值为:18,索引为:6
目标元素【28】大于中间值【18】,接下来从索引start=7到索引end=8进行检索
从索引start=7到索引end=8,要检索的数组范围为:[28, 30]
此时要检索的数组的中间值为:28,索引为:7
目标元素【28】等于中间值【28】,找到数据,索引值为:7
游标方式实现二分查找法查询结果(索引值):7

结语

  可能有些小伙伴不知道,索引 加1或者减1 的原因:

  • 关于数组,假设一个数组的长度是 9 ,数组的下标是从 0 开始的,最大的下标就是 8 ,最后一个元素就是 a[8] ,相对长度来说,数组的索引就是 数组长度减1
  • 关于中间值比较的索引,因为二分查找中要求顺序存储并且是有序排列,如果是递增的,也就是左边的数据小于中间值,右边的数据大于中间值,中间值的索引是 midIndex ,查找的值比中间值小,则我们只需要比较开始索引到 midIndex-1 这一段数据了,查找的值比中间值小,则我们只需要比较 midIndex+1 到结束索引这一段数据了,如果是递减的,就反过来就行了

  多看两边我按个数据流向的图就容易理解了,希望你也能掌握。

相关文章:

  • [前缀和]Tokitsukaze and Strange Inequality Codeforces1678C
  • Stl中map、set 容器(数据结构:AVL树、红黑树)--C++
  • Chapter20: Machine Learning for In Silico ADMET Prediction
  • Ubuntu下安装Miniconda
  • No1.搭建基本的密码模式请求token(授权服务端)
  • 代码随想录二叉树——从中序与后序遍历序列构造二叉树
  • 【2023泰凌微笔试题】~ 题目及参考答案
  • 采用Python中Tkinter模块的Treeview 组件显示xml文件
  • synchronized的实现原理与应用
  • 网上商城之支付
  • 一次搞懂Java如何调用Kotlin的高级特性
  • MyBatis各种SQL操作及执行添加功能获取自增的主键
  • 【学习笔记】模拟赛题解
  • node.js 使用教程-3.gulp-file-include 详细教程
  • 【可视化大屏教程】用Python开发智慧城市数据分析大屏
  • 【跃迁之路】【477天】刻意练习系列236(2018.05.28)
  • classpath对获取配置文件的影响
  • CSS相对定位
  • iOS编译提示和导航提示
  • Java读取Properties文件的六种方法
  • js中的正则表达式入门
  • Promise面试题,控制异步流程
  • ViewService——一种保证客户端与服务端同步的方法
  • Vue官网教程学习过程中值得记录的一些事情
  • Webpack入门之遇到的那些坑,系列示例Demo
  • Yii源码解读-服务定位器(Service Locator)
  • 阿里云Kubernetes容器服务上体验Knative
  • 京东美团研发面经
  • 开年巨制!千人千面回放技术让你“看到”Flutter用户侧问题
  • 蓝海存储开关机注意事项总结
  • 免费小说阅读小程序
  • 前端技术周刊 2019-01-14:客户端存储
  • 如何在 Tornado 中实现 Middleware
  • 软件开发学习的5大技巧,你知道吗?
  • 深度解析利用ES6进行Promise封装总结
  • 通过获取异步加载JS文件进度实现一个canvas环形loading图
  • 微服务入门【系列视频课程】
  • 源码安装memcached和php memcache扩展
  • #define,static,const,三种常量的区别
  • #预处理和函数的对比以及条件编译
  • $forceUpdate()函数
  • (10)Linux冯诺依曼结构操作系统的再次理解
  • (Bean工厂的后处理器入门)学习Spring的第七天
  • (C#)if (this == null)?你在逗我,this 怎么可能为 null!用 IL 编译和反编译看穿一切
  • (C#)获取字符编码的类
  • (done) NLP “bag-of-words“ 方法 (带有二元分类和多元分类两个例子)词袋模型、BoW
  • (Pytorch框架)神经网络输出维度调试,做出我们自己的网络来!!(详细教程~)
  • (附源码)小程序 交通违法举报系统 毕业设计 242045
  • (机器学习-深度学习快速入门)第一章第一节:Python环境和数据分析
  • (十八)用JAVA编写MP3解码器——迷你播放器
  • (转) ns2/nam与nam实现相关的文件
  • (转)人的集合论——移山之道
  • .gitignore文件—git忽略文件
  • .net core使用ef 6
  • .NET 反射的使用