Java【数据结构】二分查找
🌞 题目:
🌏在有序数组A中,查找目标值target
🌏如果找到返回索引
🌏如果找不到返回-1
算法描述 | 解释 |
---|---|
前提 | 给定一个内含n个元素的有序数组A,满足A0<=A1<=A2<=·······<=An-1,一个待查值target |
1 | 设置left=0;right = n - 1 |
2 | 如果left > right ,结束查找,没找到 |
3 | 设置mid = (left + right )/2,mid为中间索引 |
4 | 如果target < Am,设置right = mid -1,跳到第2步 |
5 | 如果target > Am,设置left = mid +1,跳到第2步 |
6 | 如果Am = target,结束查找,找到了 |
算法实现
public int binarySearch(int[] arr,int target) {int left = 0;int right = arr.length-1;while(left<=right) {int mid = (left+right)>>>1;if(target < arr[mid]) {right = mid - 1;}else if (arr[mid] < target) {left = mid + 1;}else {return mid;}}return -1;}
注解:
1.为什么while循环条件是left<=right,而不是left<right?
因为当left=right时,mid=left=right可能为我们想要查找的值
2.为什么mid = (left+right)>>>1,而不是(left+right)/2呢? >>>是无符号右移,无符号右移一位相当于除2取整。 不用(left+right)/2原因是,当left+right的值超过int类型的正整数最大范围,其值就会由正变负
在其他的资料中二分查找与这个代码不一样,
✈️ 二分查找的改动版
public static int binarySearch1(int[] arr,int target) {int left=0;int right = arr.length; //第一处改动while(left < right) { //第二处改动int mid = (left+right)>>>1;if(target < arr[mid]) {right = mid; //第三处改动}else if (arr[mid] < target) {left = mid + 1;}else {return mid;}}return -1;}
⛵️注解:
right=arr.length,作为一个边界存在,left可能为我们的查找目标,但是right一定不是我们要找到的目标
🚀图解演示:
查找13
⛽️在Java中其实已经提供了二分查找的方法binarySearch
public class Test {public static void main(String[] args) {int[] arr ={1,2,3,4,5,5,6};int target = Arrays.binarySearch(arr,3);System.out.println(target);}
}
🚠运行结果:
2
🚩二分查找对重复元素的处理
📍重复元素最靠右的元素
说明:查找元素为重复元素的话,会查找到最右边的重复元素
Returns:
找到则返回最靠右索引
找不到返回-1
//重复元素最靠右的元素
public class Test5 {public static int binarySearch2(int[] arr,int target) {int left = 0;int right = arr.length-1;int cand = -1;while (left <= right) {int mid = (left + right)>>>1;if(target < arr[mid]) {right = mid-1;} else if (arr[mid] < target) {left = mid+1;}else {cand = mid;left = mid+1;}}return cand;}
}
说明:返回<=target的最右边的索引
Returns:
找到则返回最靠右索引
找不到返回小于target最右边的索引
public static int binarySearchRightMost(int[] arr,int target){int left = 0;int right = arr.length-1;while(left <= right) {int mid = (left + right )>>>1;if(target < arr[mid]){right = mid-1;}else {left = mid + 1;}}return left-1;}
📍重复元素最靠左的元素
说明:查找元素为重复元素的话,会查找到最左边的重复元素
Returns:
找到则返回最靠左索引
找不到返回-1
public static int binarySearch2(int[] arr,int target) {int left = 0;int right = arr.length-1;int cand = -1;while (left <= right) {int mid = (left + right)>>>1;if(target < arr[mid]) {right = mid-1;} else if (arr[mid] < target) {left = mid+1;}else {cand = mid;right = mid - 1;}}return cand;}
说明:
返回>=target最左边的索引
Returns:
找到则返回最靠左索引
找不到返回比target大的最左边索引
public static int binarySearchLeftMost(int[] arr,int target) {int left=0;int right = arr.length-1;while(left <= right) {int mid = (left + right)>>>1;if(target <= arr[mid]) {right = mid - 1;}else {left = mid + 1;}}return left;}
图解:
🚆leetcode二分查找题
1️⃣1.给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
⏩ 链接: 二分查找
提示:
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999,9999]之间。
class Solution {public int search(int[] nums, int target) {int i=0;int j = nums.length-1;while(i<=j){int m=(i+j)>>>1;if(target<nums[m]){j=m-1;}else if(nums[m]<target){i=m+1;}else{return m;}}return -1;}
}
2️⃣2.给定一个排序的整数数组 nums 和一个整数目标值 target ,请在数组中找到 target ,并返回其下标。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
⏩ 链接: 搜索插入位置
class Solution {public int searchInsert(int[] nums, int target) {int left=0;int right = nums.length-1;while(left <= right) {int mid = (left + right)>>>1;if(target <= nums[mid]) {right = mid - 1;}else {left = mid + 1;}}return left;}
}
3️⃣3.给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target,返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
⏩ 链接: 在排序数组中查找元素的第一个和最后一个位置
class Solution {public int[] searchRange(int[] nums, int target) {int x=left(nums,target);if(x==-1){return new int[]{-1,-1};}else{return new int[]{x,right(nums,target)};}}public int left(int[] nums,int target) {int i=0;int j=nums.length-1;int cand=-1;while(i<=j){int m=(i+j)>>>1;if(target<nums[m]){j=m-1;}else if(nums[m]<target){i=m+1;}else{cand=m;j=m-1;}}return cand;}public int right(int[] nums,int target) {int i=0;int j=nums.length-1;int cand=-1;while(i<=j){int m=(i+j)>>>1;if(target<nums[m]){j=m-1;}else if(nums[m]<target){i=m+1;}else{cand=m;i=m+1;}}return cand;}
}
相关文章:

Java【数据结构】二分查找
🌞 题目: 🌏在有序数组A中,查找目标值target 🌏如果找到返回索引 🌏如果找不到返回-1 算法描述解释前提给定一个内含n个元素的有序数组A,满足A0<A1<A2<<An-1,一个待查值target1设…...

数据库技术--数据库引擎,数据访问接口及其关系详解(附加形象的比喻)
目录 背景数据库引擎Jet数据库:ISAM:ODBC(Open Database Connectivity): 数据访问接口ADO(ActiveX Data Objects)DAO(Data Access Objects)RDO(Remote Data O…...
【BASH】回顾与知识点梳理(三十三)
【BASH】回顾与知识点梳理 三十三 三十三. 认识系统服务 (daemons)33.1 什么是 daemon 与服务 (service)早期 System V 的 init 管理行为中 daemon 的主要分类 (Optional)systemd 使用的 unit 分类systemd 的配置文件放置目录systemd 的 unit 类型分类说明 33.2 透过 systemctl…...

同步请求和异步请求
同步请求和异步请求是在网络编程中常用的两种通信模式,它们有以下区别: 同步请求: 在发送一个请求后,程序会一直等待服务器返回响应,期间无法进行其他操作。请求发出后,程序会阻塞在请求处,直…...

Transformer是什么,Transformer应用
目录 Transformer应用 Transformer是什么 Transformer应用:循环神经网络 语言翻译:注重语句前后顺序 RNN看中单个特征; CNN:看中特征之间时序性 模型关注不同位置的能力 Transformer是什么 Transformer是一个利用注意力机制来提高模型训练速度的模型。关于注意力机…...

故障011:dmap服务缺失libnsl.so修复
故障011:dmap服务缺失libnsl.so修复 1. 问题描述2. 解决方法2.1 初步分析2.2 动手实操2.2.1 模糊搜索大法2.2.2 僵桃代李大法 DM技术交流QQ群:940124259 1. 问题描述 今天遇二期XC环境,达梦DM 7.6的DmAPService备份辅助进程服务无法启动&a…...

第十三章 SpringBoot项目(总)
1.创建SpringBoot项目 1.1.设置编码 1.4.导入已有的spring boot项目 2.快速搭建Restfull风格的项目 2.1.返回字符串 RestController public class IndexController {RequestMapping("/demo1")public Object demo1() {System.out.println("demo1 ran...."…...

利用Python隧道爬虫ip轻松构建全局爬虫网络
嘿,爬虫程序员们!你们有没有碰到过需要大规模数据爬取的情况?也许你们之前遇到过网站的反爬措施,卡住你们的进度。别担心,今天我来分享一个利用Python隧道爬虫ip实现的方法,帮助你们轻松搭建全局爬虫ip网络…...

Spring Clould 网关 - Gateway
视频地址:微服务(SpringCloudRabbitMQDockerRedis搜索分布式) Gateway网关-网关作用介绍(P35) Spring Cloud Gateway 是 Spring Cloud 的一个全新项目,该项目是基于 Spring 5.0,Spring Boot 2…...

PHP使用phpmailer及SMTP服务实现邮件发送
博客升级中,把之前没有想到的功能一点点的完善。 这篇日志记录一下,使用phpmailer实现邮件发送的这样一个操作。 博客偶尔会有留言和评论,我也会及时回复,但是有一个问题,我回复了,给我留言的人如果不再次…...

交换实验一
题目 交换机上接口配置 SW1 interface GigabitEthernet0/0/1 port hybrid tagged vlan 2 port hybrid untagged vlan 3 to 6 interface Ethernet0/0/2 port hybrid pvid vlan 3 port hybrid untagged vlan 2 to 6 interface Ethernet0/0/3 port link-type access port d…...

计算机中丢失MSVCR120.dll,找不到MSVCR120.dll是什么意思?
当计算机中缺少MSVCR120.dll文件时,意味着缺少了Microsoft Visual C Redistributable文件的一个组件。MSVCR120.dll是Visual C Redistributable 2013的动态链接库文件,它是应用程序依赖的重要文件之一。缺少MSVCR120.dll文件可能会导致一些应用程序无法正…...

avue多选列表根据后端返回的某个值去判断是否选中;avue-curd多选回显
效果如上: getSiteList().then(res > {//列表数据this.siteData res.data.datathis.$nextTick(()>{this.siteData.forEach(item>{//业务条件if(item.configid&&item.configid!0&&item.configid>0){//符合条件时调用选中的方法this.$…...

Vue2中根据权限添加动态路由
Vue2中根据权限添加动态路由 大概记录一下主要代码 1.根据后端返回的路由列表生成左侧菜单(后端返回的数据结构中用id和pid来区别包含关系) 大概结构如下: 2.前端需要处理成包含children的树形结构 //动态生成菜单 export const gener…...

搭建 Python 环境 | Python、PyCharm
计算机 计算机能完成的工作: 算术运算逻辑判断数据存储网络通信…更多的更复杂的任务 以下这些都可以称为 “计算机”: 一台计算机主要由以下这几个重要的组件构成 CPU 中央处理器:大脑,算术运算,逻辑判断 存储器&…...
NPOI 读取和写入Excel
在C#中使用NPOI库读取和写入Excel文件,你需要先下载并安装NPOI库。你可以在NuGet管理器中搜索NPOI并进行安装。 以下是一个使用NPOI库进行Excel文件读取和写入的示例: 读取Excel文件: using NPOI.SS.UserModel; using NPOI.XSSF.UserModel…...

Linux工具【2】(调试器gdb、项目自动化构建工具make/Makefile)
gdb、make/Makefile 引言调试器gdb介绍常用指令 自动化构建工具make/Makefile介绍使用依赖关系与依赖方法编辑Makefile伪目标 总结 引言 在上一篇文章中介绍了Linux中的编辑器vim与编译器gcc与g: 戳我看vim与gcc详解哦 在本篇文章中将继续来介绍Linux中的工具&…...

C++ 网络编程项目fastDFS分布式文件系统(三)-Nginx部分
目录 1. 一些基本概念 1.1 Nginx初步认识 1.2 正向/反向代理 1.3 域名和IP 2. Nginx 安装和配置 2.1 安装 2.2 配置 3. Nginx的使用 3.1 部署静态网页 3.2 反向代理和负载均衡 4 课外知识导读 1. URL和URI 编辑 2. DNS解析过程 1. 一些基本概念 1.1 Nginx初步认…...

Apache-DBUtils
目录 封装方法 引出dbutils 案例 当关闭connection后,resultset结果集就无法使用了,这就使得resultset不利于数据的管理 封装方法 我们可以将结果集先存储在一个集合中,当connection关闭后,我们可以通过访问集合来访问结果集 …...

LangChain手记 Agent 智能体
整理并翻译自DeepLearning.AILangChain的官方课程:Agent(源代码可见) “人们有时会将LLM看作是知识库,因为它被训练所以记住了来自互联网或其他地方的海量信息,因而当你向它提问时,它可以回答你的问题。有一…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...
pycharm 设置环境出错
pycharm 设置环境出错 pycharm 新建项目,设置虚拟环境,出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...
鸿蒙(HarmonyOS5)实现跳一跳小游戏
下面我将介绍如何使用鸿蒙的ArkUI框架,实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

实战设计模式之模板方法模式
概述 模板方法模式定义了一个操作中的算法骨架,并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下,重新定义算法中的某些步骤。简单来说,就是在一个方法中定义了要执行的步骤顺序或算法框架,但允许子类…...