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

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【数据结构】二分查找

&#x1f31e; 题目&#xff1a; &#x1f30f;在有序数组A中&#xff0c;查找目标值target &#x1f30f;如果找到返回索引 &#x1f30f;如果找不到返回-1 算法描述解释前提给定一个内含n个元素的有序数组A&#xff0c;满足A0<A1<A2<<An-1,一个待查值target1设…...

数据库技术--数据库引擎,数据访问接口及其关系详解(附加形象的比喻)

目录 背景数据库引擎Jet数据库&#xff1a;ISAM&#xff1a;ODBC&#xff08;Open Database Connectivity&#xff09;&#xff1a; 数据访问接口ADO&#xff08;ActiveX Data Objects&#xff09;DAO&#xff08;Data Access Objects&#xff09;RDO&#xff08;Remote Data O…...

【BASH】回顾与知识点梳理(三十三)

【BASH】回顾与知识点梳理 三十三 三十三. 认识系统服务 (daemons)33.1 什么是 daemon 与服务 (service)早期 System V 的 init 管理行为中 daemon 的主要分类 (Optional)systemd 使用的 unit 分类systemd 的配置文件放置目录systemd 的 unit 类型分类说明 33.2 透过 systemctl…...

同步请求和异步请求

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

Transformer是什么,Transformer应用

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

故障011:dmap服务缺失libnsl.so修复

故障011&#xff1a;dmap服务缺失libnsl.so修复 1. 问题描述2. 解决方法2.1 初步分析2.2 动手实操2.2.1 模糊搜索大法2.2.2 僵桃代李大法 DM技术交流QQ群&#xff1a;940124259 1. 问题描述 今天遇二期XC环境&#xff0c;达梦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轻松构建全局爬虫网络

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

Spring Clould 网关 - Gateway

视频地址&#xff1a;微服务&#xff08;SpringCloudRabbitMQDockerRedis搜索分布式&#xff09; Gateway网关-网关作用介绍&#xff08;P35&#xff09; Spring Cloud Gateway 是 Spring Cloud 的一个全新项目&#xff0c;该项目是基于 Spring 5.0&#xff0c;Spring Boot 2…...

PHP使用phpmailer及SMTP服务实现邮件发送

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

交换实验一

题目 交换机上接口配置 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文件时&#xff0c;意味着缺少了Microsoft Visual C Redistributable文件的一个组件。MSVCR120.dll是Visual C Redistributable 2013的动态链接库文件&#xff0c;它是应用程序依赖的重要文件之一。缺少MSVCR120.dll文件可能会导致一些应用程序无法正…...

avue多选列表根据后端返回的某个值去判断是否选中;avue-curd多选回显

效果如上&#xff1a; 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.根据后端返回的路由列表生成左侧菜单&#xff08;后端返回的数据结构中用id和pid来区别包含关系&#xff09; 大概结构如下&#xff1a; 2.前端需要处理成包含children的树形结构 //动态生成菜单 export const gener…...

搭建 Python 环境 | Python、PyCharm

计算机 计算机能完成的工作&#xff1a; 算术运算逻辑判断数据存储网络通信…更多的更复杂的任务 以下这些都可以称为 “计算机”&#xff1a; 一台计算机主要由以下这几个重要的组件构成 CPU 中央处理器&#xff1a;大脑&#xff0c;算术运算&#xff0c;逻辑判断 存储器&…...

NPOI 读取和写入Excel

在C#中使用NPOI库读取和写入Excel文件&#xff0c;你需要先下载并安装NPOI库。你可以在NuGet管理器中搜索NPOI并进行安装。 以下是一个使用NPOI库进行Excel文件读取和写入的示例&#xff1a; 读取Excel文件&#xff1a; using NPOI.SS.UserModel; using NPOI.XSSF.UserModel…...

Linux工具【2】(调试器gdb、项目自动化构建工具make/Makefile)

gdb、make/Makefile 引言调试器gdb介绍常用指令 自动化构建工具make/Makefile介绍使用依赖关系与依赖方法编辑Makefile伪目标 总结 引言 在上一篇文章中介绍了Linux中的编辑器vim与编译器gcc与g&#xff1a; 戳我看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后&#xff0c;resultset结果集就无法使用了&#xff0c;这就使得resultset不利于数据的管理 封装方法 我们可以将结果集先存储在一个集合中&#xff0c;当connection关闭后&#xff0c;我们可以通过访问集合来访问结果集 …...

LangChain手记 Agent 智能体

整理并翻译自DeepLearning.AILangChain的官方课程&#xff1a;Agent&#xff08;源代码可见&#xff09; “人们有时会将LLM看作是知识库&#xff0c;因为它被训练所以记住了来自互联网或其他地方的海量信息&#xff0c;因而当你向它提问时&#xff0c;它可以回答你的问题。有一…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 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 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

pycharm 设置环境出错

pycharm 设置环境出错 pycharm 新建项目&#xff0c;设置虚拟环境&#xff0c;出错 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框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

实战设计模式之模板方法模式

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