Java算法:二分查找

一、 二分查找注意

        前提是数组必须是有序的,否则无法正常工作。如果数组不是有序的,需要先对数组进行排序,然后才能使用二分查找算法。

二、二分查找高效算法

    二分查找也称为折半查找,是一种在有序数组中查找目标元素的算法。它的原理是不断将查找范围减半,直到找到目标元素或确定目标元素不存在。

     在一个有序数组中查找特定元素时,二分查找是一种高效的算法。它的时间复杂度为 O(log n),相较于线性查找的 O(n),二分查找可以显著提高搜索效率。

三、二分查找步骤

初始化左边界 left 为数组第一个元素的索引,右边界 right 为数组最后一个元素的索引。
计算中间元素的索引 mid=(left + right) / 2。
比较中间元素与目标元素:
        如果中间元素=目标元素,则找到目标,返回中间元素的索引。
        如果中间元素>目标元素,则将右边界更新为 mid - 1,继续在左半边查找。
        如果中间元素<目标元素,则将左边界更新为 mid + 1,继续在右半边查找。

四、 Java 实现二分查找

    //测试数据
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        List<Integer> list = getList();
        System.out.println(list);
        while(true) {
            System.out.print("输入查找的数字:");
            int find_num = sc.nextInt();
            Integer num = search(list, find_num);
            System.out.println(num);
        }
    }

    /**
     * (2)二分查找法:
     * @param list
     * @param number
     * @return
     */
    private static Integer search(List<Integer> list, int number) {
        //左边位置
        int low = 0;
        //右边位置
        int high = list.size() - 1;
        //循环
        while (low <= high) {
            //中间元素
            int mid = (low + high) / 2;
            //获取中间元素
            int guess = list.get(mid);
            //判断
            if (guess == number) { //找到这个元素
                return mid;
            } else if (guess > number) { //中间元素大于输入的目标数据,继续在left半边查找
                high = mid - 1;
            } else {  //中间元素小于输入的目标数据,继续在right半边查找
                low = mid + 1;
            }
        }
        return -1;  //找不到元素,则返回-1
    }

    /**
     * (1) 有序列表数据20个随机生成
     */
    private static List<Integer> getList() {
        //过滤重复的数据
        Set<Integer> sets = new HashSet<>();
        Random random = new Random();
        while (true) {
            //生成1-50的随机数
            int ran = random.nextInt(50) + 1;
            //添加
            sets.add(ran);
            //判断生成20个数据
            if (sets.size() >= 20) {
                break;
            }
        }
        //集合数据
        List<Integer> list = new ArrayList<>(sets);
        //升序排序
        Collections.sort(list);
        return list;
    }

效果:

优点和缺点

       二分查找算法的主要优点是其时间复杂度为O(log n),因此对于大型数组的查找操作非常高效。此外,由于二分查找是基于数组的有序性进行查找的,因此可以应用于静态数据集合中的查找操作。

      二分查找也存在一些明显的缺点。首先,二分查找只适用于有序数组,因此如果需要在无序的数据集中查找元素,则需要事先对数据进行排序。其次,二分查找不适用于动态数据结构,因为在插入或删除元素后,会破坏数组的有序性,需要重新排序才能再次使用二分查找

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/112896.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【嵌入式开发学习02】esp32cam烧录human_face_detect实现人脸识别

Ubuntu20.04系统为esp32cam烧录human_face_detect 1. 下载esp-dl2. 安装esp-idf3. 烧录human_face_detect 如果使用ubuntu 16.04在后续的步骤中会报错如下&#xff0c;因为ubuntu 16.04不支持glibc2.23以上的版本&#xff08;可使用strings /lib/x86_64-linux-gnu/libc.so.6 | …

护眼灯有没有护眼的效果?适合学生儿童的五款护眼台灯推荐

如果不想家里的孩子年纪小小的就戴着眼镜&#xff0c;从小就容易近视&#xff0c;那么护眼灯的选择就非常重要了&#xff0c;但是市场上那么多品类&#xff0c;价格也参差不齐&#xff0c;到底怎么选呢&#xff1f;大家一定要看完本期内容。为大家推荐最热门的五款护眼台灯。 1…

HTML、CSS和JavaScript,实现换肤效果的原理

这篇涉及到HTML DOM的节点类型、节点层级关系、DOM对象的继承关系、操作DOM节点和HTML元素 还用到HTML5的本地存储技术。 换肤效果的原理&#xff1a;是在选择某种皮肤样式之后&#xff0c;通过JavaScript脚本来加载选中的样式&#xff0c;再通过localStorage存储。 先来回忆…

Spring MVC (Next-1)

1.Restful请求 restFul是符合rest架构风格的网络API接口,完全承认Http是用于标识资源。restFul URL是面向资源的&#xff0c;可以唯一标识和定位资源。 对于该URL标识的资源做何种操作是由Http方法决定的。 rest请求方法有4种&#xff0c;包括get,post,put,delete.分别对应获取…

CRM系统数据库是如何影响客户体验的?

CRM客户关系管理由概念到软件实体&#xff0c;已经有几十年的时间&#xff0c;随着信息技术的进步&#xff0c;数字化让CRM软件乘上快车&#xff0c;迅速成为各类企业的数字化管理工具。CRM客户管理系统的一个重要功能便是改善并提升客户体验&#xff0c;且CRM数据库是与客户体…

【笔记】excel怎么把汉字转换成拼音

1、准备好excel文件&#xff0c;复制需要转拼音列。 2、打开一个空白Word文档&#xff0c;并粘贴刚才复制的内容&#xff1b; 3、全选Word文档中刚粘贴的内容&#xff0c;点击「开始」选项卡「字体」命令组下的「拼音指南」&#xff0c;调出拼音指南对话框&#xff1b; 4、全…

如何调整职场心态,提高工作表现

文章目录 介绍职场分析对比历年职场需求开发者地域分布开发者工作状态职场晋升之路 职场经验控制情绪保持好奇心提升核心能力 职场转行结论 介绍 职场中的心态调整对于我们在工作中表现的影响非常重要。作为一名全栈开发者&#xff0c;我深知在 AI 算法和云技能领域工作的挑战…

【生物信息学】单细胞RNA测序数据分析:计算亲和力矩阵(基于距离、皮尔逊相关系数)及绘制热图(Heatmap)

文章目录 一、实验介绍二、实验环境1. 配置虚拟环境2. 库版本介绍 三、实验内容0. 导入必要的库1. 读取数据集2. 质量控制&#xff08;可选&#xff09;3. 基于距离的亲和力矩阵4. 绘制基因表达的Heatmap5. 基于皮尔逊相关系数的亲和力矩阵6. 代码整合 一、实验介绍 计算亲和力…

云服务器 centos 部署 code-server 并配置 c/c++ 环境

将你的云服务器改为 centos 8 为什么要将云服务器的操作系统改成 centos 8 呢&#xff1f;原因就是 centos 7 里面的配置满足不了 code-server 的需求。如果你使用的是 centos 7 那么就需要你升级一些东西&#xff0c;这个过程比较麻烦。我在 centos 7 上面运行 code-server 的…

[学习笔记]python绘制图中图(绘制站点分布图)

背景 在绘制站点分布图时&#xff0c;有时需要采用图中图的方式&#xff0c;以便于在一张图中尽可能多的表达信息。此处记录一下利用python matplotlib绘制图中图的脚本&#xff0c;方便然后查询。 包含数据 该绘图脚本中包含以下数据&#xff1a; CMONOC站点分布&#xff…

CCF_A 计算机视觉顶会CVPR2024投稿指南以及论文模板

目录 CVPR2024官网&#xff1a; CVPR2024投稿链接&#xff1a; CVPR2024 重要时间节点&#xff1a; CVPR2024投稿模板: WORD: LATEX : CVPR2024_AuthorGuidelines CVPR2024投稿Topics&#xff1a; CVPR2024官网&#xff1a; https://cvpr.thecvf.com/Conferences/2024CV…

pytorch复现4_Resnet

ResNet在《Deep Residual Learning for Image Recognition》论文中提出&#xff0c;是在CVPR 2016发表的一种影响深远的网络模型&#xff0c;由何凯明大神团队提出来&#xff0c;在ImageNet的分类比赛上将网络深度直接提高到了152层&#xff0c;前一年夺冠的VGG只有19层。Image…

正点原子嵌入式linux驱动开发——Linux USB驱动

USB是很常用的接口&#xff0c;目前大多数的设备都是USB接口的&#xff0c;比如鼠标、键盘、USB摄像 头等&#xff0c;在实际开发中也常常遇到USB接口的设备&#xff0c;本章就来学习一下如何使能Linux内核自带的USB驱动。这里不会具体学习USB的驱动开发。 USB接口简介 什么是…

常用sql语句

/*表操作*/ drop table order; create table products( product_no integer primary key default 1, name text, price numeric default 9.99 ); create table orders ( order_id integer primary key default 1, product_no int, quantity integer ); create table order_…

目标检测:Proposal-Contrastive Pretraining for Object Detection from Fewer Data

论文作者&#xff1a;Quentin Bouniot,Romaric Audigier,Anglique Loesch,Amaury Habrard 作者单位&#xff1a;Universit Paris-Saclay; Universit Jean Monnet Saint-Etienne; Universitaire de France (IUF) 论文链接&#xff1a;http://arxiv.org/abs/2310.16835v1 内容…

ztree调整节点间距及一般使用

1.基本介绍 树形结构菜单的功能属于非常常见的一种菜单交互&#xff0c;本人先后也使用过多种树形结构的插件&#xff0c;有 ztree、xloadtree、treeview、datagrid-tree 等等等等。近期有个功能恰好又要使用tree菜单了&#xff0c;由于可自行选择使用的组件&#xff0c;所以略…

微信小程序 人工智能志愿者服务活动报名系统uniAPP+vue

基于java语言设计并实现了人工智能志愿者服务APP。该APP基于B/S即所谓浏览器/服务器模式&#xff0c;应用SpringBoot框架与HBuilder X技术&#xff0c;选择MySQL作为后台数据库。系统主要包括用户、志愿活动、活动报名、活动签到、服务职责、服务排行等功能模块。 本文首先介绍…

【2021集创赛】Risc-v杯一等奖:自适应噪声环境的超低功耗语音关键词识别系统

本作品参与极术社区组织的有奖征集|秀出你的集创赛作品风采,免费电子产品等你拿~活动。 团队介绍 参赛单位&#xff1a;东南大学 队伍名称&#xff1a;Hey Siri 指导老师&#xff1a;刘波 参赛队员&#xff1a;钱俊逸、张人元、王梓羽 总决赛奖项&#xff1a;全国一等奖 摘要…

数字孪生技术:金融业合规与自动化的未来

在当今数字化时代&#xff0c;金融行业正积极探索数字孪生技术&#xff0c;以实现更高效的运营和更好的客户体验。数字孪生是一种将实体世界的对象、过程和系统数字化为虚拟模型的技术&#xff0c;金融机构正在充分利用它带来的众多优势。 1. 风险管理与模拟 数字孪生模型可用…

docker部署minio并使用springboot连接

需求&#xff1a;工作中&#xff0c;在微信小程序播放时&#xff0c;返回文件流并不能有效的使用&#xff0c;前端需要一个可以访问的地址&#xff0c;springboot默认是有资源拦截器的&#xff0c;但是不适合生产环境的使用 可以提供使用的有例如fastdfs或者minio&#xff0c;这…