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

二分查找基础篇-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

一、概述&#xff1a; 基于VC MSSQL实现的一套三甲医院医学影像PACS源码&#xff0c;集成3D后处理功能&#xff0c;包括三维多平面重建、三维容积重建、三维表面重建、三维虚拟内窥镜、最大/小密度投影、心脏动脉钙化分析等功能。 二、医学影像PACS实现功能&#xff1a; 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 配置文件调整&#xff08;一劳永逸&#xff09; 2、Jmeter线程组基本操作2.1 线程组是什么2.2 线程组2.2.1 创建线程组2.2…...

如何在云上部署java项目

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

IT行业项目管理软件,你知道多少?

IT行业项目管理软件&#xff0c;主要得看用来管理的是软件研发还是做IT运维。如果是做软件研发&#xff0c;那还得看项目经理是用什么思路&#xff0c;是传统的瀑布式方法还是敏捷的方法或者是混合的方法。 如果用来管理的是IT运维工作&#xff0c;那么很多通用型的项目管理软件…...

小爱同学接入chatGPT

大致流程 最近入手了一款小爱音响&#xff0c;想着把小爱音响接入 chatGPT, 在 github 上找了一个非常优秀的开源项目&#xff0c;整个过程还是比较简单的&#xff0c;一次就完成了。 其中最难的技术点是 如何获取与小爱的对话记录&#xff1f;如何让小爱播放文本&#xff1f…...

java运算符

1.运算符和表达式 运算符&#xff1a; ​ 就是对常量或者变量进行操作的符号。 ​ 比如&#xff1a; - * / 表达式&#xff1a; ​ 用运算符把常量或者变量连接起来的&#xff0c;符合Java语法的式子就是表达式。 ​ 比如&#xff1a;a b 这个整体就是表达式。 ​ 而其…...

StrongSORT_文献翻译

StrongSORT 【摘要】 现有的MOT方法可以被分为tracking-by-detection和joint-detection-association。后者引起了更多的关注&#xff0c;但对于跟踪精度而言&#xff0c;前者仍是最优的解决方案。StrongSORT在DeepSORT的基础之上&#xff0c;更新了它的检测、嵌入和关联等多个…...

Python每日一练(20230512) 跳跃游戏 V\VI\VII

目录 1. 跳跃游戏 V 2. 跳跃游戏 VI 3. 跳跃游戏 VII &#x1f31f; 每日一练刷题专栏 &#x1f31f; 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&#xff08;卡琳玛乔丽&#xff09;正同时交往1000多个男朋友。 作为一个在Snapchat上坐拥180万粉丝的美女&#xff0c;她利用人工智能&#xff08;AI&#xff09;技术&#xff0c;打造了一个AI版本的自己&#x…...

如何修复d3dcompiler_47.dll缺失?多种解决方法分享

在使用Windows操作系统的过程中&#xff0c;有时候会遇到d3dcompiler_47.dll缺失的情况。这个问题可能会导致某些应用程序无法正常运行&#xff0c;因此需要及时解决。本文将介绍如何修复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. 原理介绍 并查集是一种用于维护集合关系的数据结构&#xff0c;它支持合并集合和查询元素所在的集合。它的基本思想是将元…...

十分钟在 macOS 快速搭建 Linux C/C++ 开发环境

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

银河麒麟系统Arm64编译opencv指南

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

蒙层禁止下方页面滚动防抖动完美方案

学习链接 js如何禁止滚动条滚动&#xff0c;但不消失&#xff01; - 这个是完美解决方案&#xff08;在线demo示例&#xff09; 解决窗口滚动条消失而导致的页面内容抖动的问题 完美解决js 禁止滚动条滚动&#xff0c;并且滚动条不消失&#xff0c;页面大小不闪动 蒙层禁止…...

微积分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…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...