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

二分查找的实现代码JAVA

二分查找

  • 一、思路
  • 二、实现代码(普通版)
  • 三、整数溢出问题
  • 四、改进代码

一、思路

1.前提: 有已排序数组A (假设已经做好)
2.定义左边界L、 右边界R,确定搜索范围,循环执行二分查找(3、4两步)
3.获取中间索引 M = Floor((L+R) 1/2)
4.中间素索引的值 A[M] 与待搜索的值T进行比较
①A[M]==T 表示找到,返回中间索引
②A[M]>T, 中间值右侧的其它元素都大于T,无需比较,中间索引左边去找,M- 1设置为右边界,重新查找
③A[M]<T, 中间值左侧的其它元素都小于T,无需比较,中间索引右边去找,M+ 1设置为左边界,重新查找
5.当L>R时, 表示没有找到,应结束循环

二、实现代码(普通版)


public class BinarySearch {public static void main(String[] args){int[] array = {1,5,8,11,19,22,31,35,40,45,48,49,50};int target=48;int idx=binarySearch(array,target);System.out.println(idx);}//二分查找,找到返回目标值下标,没找到返回-1;public static int binarySearch(int[] a,int target){int L=0;int R=a.length-1;int M;while (L<=R){M=(L+R)/2;if(a[M]==target)return M;else if(a[M]>target)R=M-1;else if(a[M]<target)L=M+1;}return -1;}
}

三、整数溢出问题

问题:上述代码中如果

int L=0;
int R=Integer.MAX_VALUE-1;

那么在第二次二分时将出现M超过int的取值范围,导致上溢出。

解决方法:
①通过等价运算解决

m=(r+l)/2==>l/2+r/2==>l+(-l/2+r/2)==>l+(r-l)/2;

②通过移位计算除法,无符号右移(因为下标非负)

m=(r+l)/2==>(l+r)>>>1

四、改进代码

public class BinarySearch {public static void main(String[] args){int[] array = {1,5,8,11,19,22,31,35,40,45,48,49,50};int target=48;int idx=binarySearch(array,target);System.out.println(idx);}//二分查找,找到返回目标值下标,没找到返回-1;public static int binarySearch(int[] a,int target){int L=0;int R=a.length-1;int M;while (L<=R){//改进代码,无符号右移计算除法M=(L+R)>>>1;if(a[M]==target)return M;else if(a[M]>target)R=M-1;else if(a[M]<target)L=M+1;}return -1;}
}

相关文章:

二分查找的实现代码JAVA

二分查找一、思路二、实现代码&#xff08;普通版&#xff09;三、整数溢出问题四、改进代码一、思路 1.前提: 有已排序数组A (假设已经做好) 2.定义左边界L、 右边界R,确定搜索范围&#xff0c;循环执行二分查找(3、4两步) 3.获取中间索引 M Floor((LR) 1/2) 4.中间素索引的值…...

cesium: 设置skybox透明并添加背景图 ( 003 )

第003个 点击查看专栏目录 本示例的目的是介绍如何在vue+cesium中设置skybox透明并添加背景图。 我们不想要黑乎乎的背景,想自定义一个背景图,然后前面显示地球。 直接复制下面的 vue+cesium源代码,操作2分钟即可运行实现效果. 文章目录 示例效果配置方式示例源代码(共70…...

【python】类的详解

注&#xff1a;最后有面试挑战&#xff0c;看看自己掌握了吗 文章目录PO verses OOPOOO当一个类很复杂的时候&#xff0c;考虑多弄一个类的改造私有类的模块化静态类verses动态类动态类查看模块源代码对象机制的基石 PyObjectPO verses OO PO PO耦合性高&#xff0c;很多过程…...

西安银行就业总结

引 进银行性价比最高的时刻是本科&#xff0c;研究生的话可以去需要研究生较多的银行&#xff0c;比如邮储或者证券类的中信建投。中信建投很香&#xff0c;要求本硕西电。研究生学历的话&#xff0c;一般情况下银行不会卡本科&#xff0c;只看最高学历&#xff0c;部分银行需…...

JavaScript Window

文章目录JavaScript Window浏览器对象模型 (BOM)Window 对象Window 尺寸其他 Window 方法JavaScript Window 浏览器对象模型 (BOM) 使 JavaScript 有能力与浏览器"对话"。 浏览器对象模型 (BOM) 浏览器对象模型&#xff08;Browser Object Model (BOM)&#xff09;…...

那些开发过程中需要遵守的开发规范

入职公司三天&#xff0c;没干啥其他活&#xff0c;基本在配置本地环境和阅读相关文档。技术方面公司基本用的是主流的技术体系&#xff0c;入职后需要先阅读阿里的开发规范和其他的一些产研文档。今天整理一些平时需要关注的阿里规约和数据库开发规范&#xff0c;方便今后在开…...

EFCore 基础入门教程

一、EFCore 基础入门教程EF 框架的简介、发展历史&#xff1b;ORM框架概念学习地址&#xff1a;https://blog.csdn.net/u011127019/article/details/129212786?spm1001.2014.3001.5502EFCore 安装&#xff0c;引入、支持的数据库学习地址&#xff1a;https://www.cnblogs.com/…...

HTML5 Drag and Drop

这是2个组合事件 dom对象分源对象和目标对象 绑定的事件也是分别区分源对象和目标对象 事件绑定 事件顺序 被拖拽元素&#xff0c;事件触发顺序是 dragstart->drag->dragend&#xff1b; 对于目标元素&#xff0c;事件触发的顺序是 dragenter->dragover->drop/…...

惠普m1136打印机驱动程序安装教程

惠普m113打印机是一款功能强大的多功能打印机&#xff0c;它能够打印、复印、扫描和传真等。如果你要使用这款打印机&#xff0c;你需要下载并安装驱动程序&#xff0c;以确保它能够在你的计算机上正常工作。在本文中&#xff0c;我们将介绍如何下载和安装惠普m1136打印机驱动程…...

数据增强,扩充了数据集,增加了模型的泛化能力

数据增强&#xff08;Data Augmentation&#xff09;是在不实质性的增加数据的情况下&#xff0c;从原始数据加工出更多的表示&#xff0c;提高原数据的数量及质量&#xff0c;以接近于更多数据量产生的价值。 其原理是&#xff0c;通过对原始数据融入先验知识&#xff0c;加工…...

MySQL/Oracle获取当前时间几天/分钟前的时间

获取当前时间 要想获取当前时间几天/分钟前的时间&#xff0c;首先要知道怎么获取当前时间&#xff1b; 对于MySQL和Oracle获取当前时间的方法是不一样的&#xff1b; MySQL&#xff1a; select NOW(); 示例&#xff1a; Oracle&#xff1a; select sysdate from dual; 示…...

如何在Wordpress中使用wp_nav_menu()在<li>及a标记中添加Class

我正在使用wp_nav_menu($args),我想将my_own_classCSS类名添加到<li>元素中以获得以下结果:<li classmy_own_class><a href>Link</a>怎么做&#xff1f;wp_nav_menu()在<li>标记中添加Class方法一&#xff1a;只需使用其他参数并为nav_menu_css_…...

Chat Support Board WordPress聊天插件 v3.5.8

功能列表 支持和聊天功能 Slack聊天完全同步 - 直接从Slack发送和接收用户信息。 立即工作 - 只需插入短码&#xff0c;即可立即安装和使用。 丰富的信息 - Dialogflow机器人发送丰富的信息。 机器人--集成一个由API.AI驱动的多语言机器人。 电子邮件通知 - 当收到回复时&#…...

2022年网络安全竞赛——数字取证调查attack.pcapng

攻击日志分析:需求环境可私信博主获取 任务环境说明: 服务器场景:PYsystem0031服务器场景操作系统:未知服务器场景FTP用户名:anonymous 密码:空从靶机服务器的FTP上下载attack.pcapng数据包文件,通过分析数据包attack.pcapng,找出黑客的IP地址,并将黑客的IP地址作为FL…...

2023最新MongoDB规范

前言 MongoDB是非关系型数据库的典型代表&#xff0c;DB-Engines Ranking 数据显示&#xff0c;近年来&#xff0c;MongoDB在 NoSQL领域一直独占鳌头。MongoDB是为快速开发互联网应用 而设计的数据库系统&#xff0c;其数据模型和持 久化策略就是为了构建高读/写的性能&#x…...

gcc的使用,调试工具gdb的使用

gcc编译 gcc编译可以分为四个步骤&#xff0c;预处理、编译、汇编、链接。 预处理命令&#xff1a;gcc -E hello.c -o hello.i编译命令&#xff1a;gcc -S hello.i -o hello.s汇编命令&#xff1a; gcc -c hello.s -o hello.o链接命令&#xff1a;gcc hello.o -o hello gcc…...

Python变量的定义和使用

定义&#xff1a;变量就是计算机内存中存储某些数据的位置的名称 形象理解变量就是一个存放东西的容器&#xff0c;该容器的名字就叫做变量&#xff0c;容器存放的东西就是变量的值 变量的组成&#xff1a; 标识&#xff1a;标识对象所储存的内存地址&#xff0c;使用内置函数i…...

SSM框架-AOP概述、Spring事务

16 spring整合mybatis 16.1 前情代码 实体类 public class Account {private Integer id;private String name;private Double money;public Integer getId() {return id;}public void setId(Integer id) {this.id id;}public String getName() {return name;}public void …...

一文搞定Android Vsync原理简析

屏幕渲染原理"现代计算机之父"冯诺依曼提出了计算机的体系结构: 计算机由运算器&#xff0c;存储器&#xff0c;控制器&#xff0c;输入设备和输出设备构成&#xff0c;每部分各司其职&#xff0c;它们之间通过控制信号进行交互。计算机发展到现在&#xff0c;已经出…...

第八届蓝桥杯省赛 C++ B组 - K 倍区间

✍个人博客&#xff1a;https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 &#x1f4da;专栏地址&#xff1a;蓝桥杯题解集合 &#x1f4dd;原题地址&#xff1a;K 倍区间 &#x1f4e3;专栏定位&#xff1a;为想参加蓝桥杯的小伙伴整理常考算法题解&#xff0c;祝大家…...

OpenStack Train版三节点部署全攻略:从CentOS 7.6配置到Dashboard上线

OpenStack Train版三节点部署实战&#xff1a;从CentOS 7.6到Dashboard的完整指南 当企业需要构建私有云平台时&#xff0c;OpenStack作为最成熟的开源IaaS解决方案之一&#xff0c;其灵活性和可扩展性备受青睐。本文将带您完成一个生产级的三节点OpenStack Train版部署&#x…...

六音音源修复工具:洛雪音乐跨版本兼容解决方案

六音音源修复工具&#xff1a;洛雪音乐跨版本兼容解决方案 【免费下载链接】New_lxmusic_source 六音音源修复版 项目地址: https://gitcode.com/gh_mirrors/ne/New_lxmusic_source 问题溯源&#xff1a;洛雪音乐的音源服务中断危机 在数字音乐生态中&#xff0c;软件版…...

如何通过智能求职助手提升职位时间筛选效率?揭秘高效求职新方法

如何通过智能求职助手提升职位时间筛选效率&#xff1f;揭秘高效求职新方法 【免费下载链接】boss-show-time 展示boss直聘岗位的发布时间 项目地址: https://gitcode.com/GitHub_Trending/bo/boss-show-time 在当今竞争激烈的就业市场中&#xff0c;职位时间筛选已成为…...

保姆级教程:用PHPStudy+红日靶场复现一次完整的内网渗透(从外网打到域控)

从零构建内网渗透实战&#xff1a;PHPStudy环境下的红日靶场攻防演练 在网络安全领域&#xff0c;内网渗透测试是检验企业防御体系完整性的重要手段。本文将带领读者使用常见的PHPStudy环境搭建红日靶场&#xff0c;通过模拟真实攻击路径&#xff0c;从外网Web渗透逐步深入内网…...

如何用anyRTC-RTMP-OpenSource打造个性化直播数据源:自定义视频采集完整指南

如何用anyRTC-RTMP-OpenSource打造个性化直播数据源&#xff1a;自定义视频采集完整指南 【免费下载链接】anyRTC-RTMP-OpenSource RTMP 推流器&#xff0c;RTMP(HLS)秒开播放器&#xff0c;直播点播&#xff0c;跨平台&#xff08;Win,IOS,Android&#xff09;开源代码 项目…...

电源管理入门-4子系统reset

之前的文章电源管理入门-1关机重启详解介绍了整机SoC的重启也可以说是reset&#xff0c;那么子系统的reset&#xff0c;例如某个驱动&#xff08;网卡、USB等&#xff09;或者某个子系统&#xff08;NPU、ISP等运行在独立的M核或者R核上的AI系统&#xff09;&#xff0c;这些零…...

告别手动处理:用快马AI一键生成你的专属批量链接效率工具

最近在整理项目文档时&#xff0c;经常需要处理大量杂乱无章的链接。手动一个个检查、格式化这些链接不仅耗时耗力&#xff0c;还容易出错。于是我开始寻找更高效的解决方案&#xff0c;最终在InsCode(快马)平台上快速实现了一个批量链接处理工具&#xff0c;整个过程比想象中简…...

Clawdbot整合Qwen3:32B效果体验:长文档理解与精准问答演示

Clawdbot整合Qwen3:32B效果体验&#xff1a;长文档理解与精准问答演示 1. 从痛点出发&#xff1a;为什么你需要这个工具 如果你经常需要处理技术文档、合同、论文或者产品手册&#xff0c;一定遇到过这样的困扰&#xff1a;面对一份几十页甚至上百页的PDF文件&#xff0c;想要…...

MedGemma-X智能助手实测:像住院总医师一样分析X光片

MedGemma-X智能助手实测&#xff1a;像住院总医师一样分析X光片 1. 重新定义影像诊断&#xff1a;从工具到助手 在放射科的日常工作中&#xff0c;我们习惯了与各种CAD&#xff08;计算机辅助诊断&#xff09;系统打交道。它们像精确但沉默的尺子&#xff0c;能在图像上标出可…...

FactoryBluePrints:颠覆性全流程工厂自动化解决方案

FactoryBluePrints&#xff1a;颠覆性全流程工厂自动化解决方案 【免费下载链接】FactoryBluePrints 游戏戴森球计划的**工厂**蓝图仓库 项目地址: https://gitcode.com/GitHub_Trending/fa/FactoryBluePrints FactoryBluePrints是戴森球计划的开源蓝图仓库&#xff0c;…...