二分查找基础篇-JAVA
文章目录
前言
大家好,我是最爱吃兽奶,这篇博客给大家介绍一下二分查找,我们先从最基本的开始讲解,再慢慢深入,把优化和变形也和大家说一下,那么,跟着我的步伐,我们一起去看看吧!
一、什么是二分查找?
二分查找(Binary Search)也称作折半查找
二分查找的效率很高,每查找一次,查找对象的数量就会减半
条件:要查找的元素集合必须有序
二、二分查找的实现
1.基础版
需求: 给定一个升序数组,要求我们查找数组中是否包含目标元素tmp,如果存在,则返回索引,不存在返回-1
接下来,我们就以这个数组为你进行讲解 int[] arr = {7, 13, 21, 30, 38, 44, 52, 53};
你可以打开你的编译器试着写写,思考之后再往下看效果更好哦
相信你已经写完了吧,那么我们来试着分析一下吧!
代码
public static int BinarySearchBalance(int [] arr,int target){// 定义左右边界int left = 0;int right = arr.length-1;// 循环终止条件 left<=rightwhile (left<=right) {int mid = (left+right)/2;if(target<arr[mid]){// 表示目标值在中间值的左边,向左缩小范围,令right = mid-1;right = mid-1;}else if(target > arr[mid]){// 表示目标值在中间值的右边,向右缩小范围,令right = mid+1;left = mid+1;}else{// target == arr[mid] 找到了,直接返回target处的下标return mid;}}// 循环结束,此时left>right,表名该数组中没有目标元素,直接返回-1return -1;} }
经过了上面的解释,你是不是恍然大明白了呢?
不理解的话,欢迎评论区留言,有需要指点的地方也请评论区留言
那么接下来,就开启我们的进阶之旅吧!
2.进阶版
我们先来思考一下,基础版的代码是否有问题?
相比你们都清楚,是有问题的,要不然怎么会有进阶版呢?
问题1: int mid = (left+right) / 2 有什么问题?
如果right的值为 Integer.MAX_VALUE-1 ,那么第二次循环时将有可能越界
当target<arr[mid]的时候,left = mid+1 ,(left+right)的值会超过int类型所能接受的最大值,会直接变成负数,导致mid为负值,在此时如果调用arr[mid] 会报异常
解决办法: int mid = (left+right)>>>1;
>>>: 无符号右移,最高位永远补零
我们在这里直接右移一位,天王老子来了mid都不可能变成负数了
问题2: 为什么left<=right 表示区间内有未比较的元素,而不是left<right?
left == right 表示它们指向的元素也会参与比较,left<right 则表示mid指向的元素参与比较
进阶版
j的位置一定不是目标元素!!!
代码
public static int BinarySearchAlternation(int[] arr,int target){int left = 0;int right = arr.length; //right 只作为边界,指向的一定不是查找目标while(left<right){// 表示left和right指向的元素不参与比较int mid = (left+right)>>>1;if(arr[mid]>target){// right 指向的元素不参与比较,不能赋值为 mid+1right = mid;} else if (arr[mid]<target) {left = mid+1;} else {return mid;}}return -1;}
总结
以上就是二分查找基础篇的内容了,想了解更多,关注作者,后续更加精彩!
相关文章:

二分查找基础篇-JAVA
文章目录 前言 大家好,我是最爱吃兽奶,这篇博客给大家介绍一下二分查找,我们先从最基本的开始讲解,再慢慢深入,把优化和变形也和大家说一下,那么,跟着我的步伐,我们一起去看看吧! 一、什么是二分查找? 二分查找(Binary Search)也称作折半查找 二分查找的效率很高,每查找一次…...

shell脚本5数组
文章目录 数组1 数组定义方法2 获取数组长度2.1 读取数组值2.2 数组切片2.3 数组替换2.4 数组删除2.5 追加数组元素 3 实验3.1 冒泡法3.2 直接选择法3.3 反排序法 数组 1 数组定义方法 数组名(value0 valuel value2 …) 数组名( [0]value [1]value [2]value …) 列表名“val…...

Kubernetes二进制部署 单节点
目录 1.环境准备 1.关闭防火墙和selinux 2.关闭swap 3.设置主机名 4.在master添加hosts 5.桥接的IPv4流量传递到iptables的链 6.时间同步 2.部署etcd集群 1.master节点部署 2.在node1与node2节点修改 3.在master1节点上进行启动 4.部署docker引擎 3.部署 Master 组…...

基于VC + MSSQL实现的县级医院医学影像PACS
一、概述: 基于VC MSSQL实现的一套三甲医院医学影像PACS源码,集成3D后处理功能,包括三维多平面重建、三维容积重建、三维表面重建、三维虚拟内窥镜、最大/小密度投影、心脏动脉钙化分析等功能。 二、医学影像PACS实现功能: 1、…...

Jmeter 压测 QPS
文章目录 1、准备工作1.1 Jmeter的基本概念1.2 Jmeter的作用1.3.Windows下Jmeter下载安装1.4 Jmeter的目录结构1.5 启动1.6 设置中文1.6.1 设置调整1.6.2 配置文件调整(一劳永逸) 2、Jmeter线程组基本操作2.1 线程组是什么2.2 线程组2.2.1 创建线程组2.2…...

如何在云上部署java项目
最近博主接了一波私活,由于上云的概念已经深入人心,客户要求博主也上云,本文将介绍上云的教程。 1.如何选择服务器 这里博主推荐阿里云服务器,阿里云云服务器ECS是一种安全可靠、弹性可伸缩的云计算服务,助您降低 IT…...

IT行业项目管理软件,你知道多少?
IT行业项目管理软件,主要得看用来管理的是软件研发还是做IT运维。如果是做软件研发,那还得看项目经理是用什么思路,是传统的瀑布式方法还是敏捷的方法或者是混合的方法。 如果用来管理的是IT运维工作,那么很多通用型的项目管理软件…...
小爱同学接入chatGPT
大致流程 最近入手了一款小爱音响,想着把小爱音响接入 chatGPT, 在 github 上找了一个非常优秀的开源项目,整个过程还是比较简单的,一次就完成了。 其中最难的技术点是 如何获取与小爱的对话记录?如何让小爱播放文本?…...
java运算符
1.运算符和表达式 运算符: 就是对常量或者变量进行操作的符号。 比如: - * / 表达式: 用运算符把常量或者变量连接起来的,符合Java语法的式子就是表达式。 比如:a b 这个整体就是表达式。 而其…...
StrongSORT_文献翻译
StrongSORT 【摘要】 现有的MOT方法可以被分为tracking-by-detection和joint-detection-association。后者引起了更多的关注,但对于跟踪精度而言,前者仍是最优的解决方案。StrongSORT在DeepSORT的基础之上,更新了它的检测、嵌入和关联等多个…...

Python每日一练(20230512) 跳跃游戏 V\VI\VII
目录 1. 跳跃游戏 V 2. 跳跃游戏 VI 3. 跳跃游戏 VII 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C每日一练 专栏 Java每日一练 专栏 1. 跳跃游戏 V 给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到&a…...

k8s部署mysql并使用nfs持久化数据
k8s部署mysql并使用nfs持久化数据 一、配置nfs服务器1.1 修改配置文件1.2. 载入配置1.3. 检查服务配置 二、创建K8S资源文件2.1 mysql-deployment.yml2.2 mysql-svc.yml 一、配置nfs服务器 参考文章: pod使用示例https://cloud.tencent.com/developer/article/1914388nfs配置…...

AI时代的赚钱思路:23岁女网红如何利用AI技术年入4亿?
一、AI技术为网红赚钱创造新途径 23岁美国网红Caryn Marjorie(卡琳玛乔丽)正同时交往1000多个男朋友。 作为一个在Snapchat上坐拥180万粉丝的美女,她利用人工智能(AI)技术,打造了一个AI版本的自己&#x…...

如何修复d3dcompiler_47.dll缺失?多种解决方法分享
在使用Windows操作系统的过程中,有时候会遇到d3dcompiler_47.dll缺失的情况。这个问题可能会导致某些应用程序无法正常运行,因此需要及时解决。本文将介绍如何修复d3dcompiler_47.dll缺失的问题。 一.什么是d3dcompiler_47.dll D3dcompiler_47.dll是Di…...

【项目实训】ATM自助取款系统
文章目录 1. 课程设计目的2. 课程设计任务与要求3. 课程设计说明书3.1 需求分析3.1.1 功能分析3.1.2 性能要求分析 3.2 概要设计3.2.1 功能模块图 3.3 详细设计3.3.1 实体类的设计3.3.2 实现数据库处理 3.4 主要程序功能流程图 4. 课程设计成果4.1 完整代码4.2 运行结果4.2.1 精…...

并查集算法
文章目录 1. 原理介绍2. 并查集的应用3. find()函数的定义与实现4. 并查集的join函数5. 路径压缩优化算法-优化find6. 路径压缩优化算法按秩合并算法 1. 原理介绍 并查集是一种用于维护集合关系的数据结构,它支持合并集合和查询元素所在的集合。它的基本思想是将元…...

十分钟在 macOS 快速搭建 Linux C/C++ 开发环境
有一个使用了 Epoll 的 C 项目,笔者平时用的 Linux 主力开发机不在身边,想在 macOS 上开发调试,但是没有 Linux 虚拟机。恰好,JetBrains CLion 的 Toolchains 配置除了使用本地环境,还支持 SSH、Docker。 笔者使用 CL…...

银河麒麟系统Arm64编译opencv指南
进入opencv官网下载版本;我这边下载的是2.4.13.6 ;根据需要下载最新的 Releases - OpenCV 拷贝进麒麟系统我这边是麒麟V10 sp1 2204;并解 cmake 在麒麟应用商城中安装; 打开cmake 设置opencv路径;builder文件夹可以自…...

蒙层禁止下方页面滚动防抖动完美方案
学习链接 js如何禁止滚动条滚动,但不消失! - 这个是完美解决方案(在线demo示例) 解决窗口滚动条消失而导致的页面内容抖动的问题 完美解决js 禁止滚动条滚动,并且滚动条不消失,页面大小不闪动 蒙层禁止…...
微积分python基础
微积分基础(python) 文章目录 微积分基础(python)1 函数与极限2 求导与微分3 不定积分4 定积分 1 函数与极限 # 导入sympy库 from sympy import * # 将x符号化 x Symbol("x") xx \displaystyle x x # 利用sympy中solve函数求解方程 X solve(x**2-10*x21,x) X pri…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...

智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...

均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...