二分查找的实现代码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
二分查找一、思路二、实现代码(普通版)三、整数溢出问题四、改进代码一、思路 1.前提: 有已排序数组A (假设已经做好) 2.定义左边界L、 右边界R,确定搜索范围,循环执行二分查找(3、4两步) 3.获取中间索引 M Floor((LR) 1/2) 4.中间素索引的值…...
cesium: 设置skybox透明并添加背景图 ( 003 )
第003个 点击查看专栏目录 本示例的目的是介绍如何在vue+cesium中设置skybox透明并添加背景图。 我们不想要黑乎乎的背景,想自定义一个背景图,然后前面显示地球。 直接复制下面的 vue+cesium源代码,操作2分钟即可运行实现效果. 文章目录 示例效果配置方式示例源代码(共70…...
【python】类的详解
注:最后有面试挑战,看看自己掌握了吗 文章目录PO verses OOPOOO当一个类很复杂的时候,考虑多弄一个类的改造私有类的模块化静态类verses动态类动态类查看模块源代码对象机制的基石 PyObjectPO verses OO PO PO耦合性高,很多过程…...
西安银行就业总结
引 进银行性价比最高的时刻是本科,研究生的话可以去需要研究生较多的银行,比如邮储或者证券类的中信建投。中信建投很香,要求本硕西电。研究生学历的话,一般情况下银行不会卡本科,只看最高学历,部分银行需…...
JavaScript Window
文章目录JavaScript Window浏览器对象模型 (BOM)Window 对象Window 尺寸其他 Window 方法JavaScript Window 浏览器对象模型 (BOM) 使 JavaScript 有能力与浏览器"对话"。 浏览器对象模型 (BOM) 浏览器对象模型(Browser Object Model (BOM))…...
那些开发过程中需要遵守的开发规范
入职公司三天,没干啥其他活,基本在配置本地环境和阅读相关文档。技术方面公司基本用的是主流的技术体系,入职后需要先阅读阿里的开发规范和其他的一些产研文档。今天整理一些平时需要关注的阿里规约和数据库开发规范,方便今后在开…...
EFCore 基础入门教程
一、EFCore 基础入门教程EF 框架的简介、发展历史;ORM框架概念学习地址:https://blog.csdn.net/u011127019/article/details/129212786?spm1001.2014.3001.5502EFCore 安装,引入、支持的数据库学习地址:https://www.cnblogs.com/…...
HTML5 Drag and Drop
这是2个组合事件 dom对象分源对象和目标对象 绑定的事件也是分别区分源对象和目标对象 事件绑定 事件顺序 被拖拽元素,事件触发顺序是 dragstart->drag->dragend; 对于目标元素,事件触发的顺序是 dragenter->dragover->drop/…...
惠普m1136打印机驱动程序安装教程
惠普m113打印机是一款功能强大的多功能打印机,它能够打印、复印、扫描和传真等。如果你要使用这款打印机,你需要下载并安装驱动程序,以确保它能够在你的计算机上正常工作。在本文中,我们将介绍如何下载和安装惠普m1136打印机驱动程…...
数据增强,扩充了数据集,增加了模型的泛化能力
数据增强(Data Augmentation)是在不实质性的增加数据的情况下,从原始数据加工出更多的表示,提高原数据的数量及质量,以接近于更多数据量产生的价值。 其原理是,通过对原始数据融入先验知识,加工…...
MySQL/Oracle获取当前时间几天/分钟前的时间
获取当前时间 要想获取当前时间几天/分钟前的时间,首先要知道怎么获取当前时间; 对于MySQL和Oracle获取当前时间的方法是不一样的; MySQL: select NOW(); 示例: Oracle: 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>怎么做?wp_nav_menu()在<li>标记中添加Class方法一:只需使用其他参数并为nav_menu_css_…...
Chat Support Board WordPress聊天插件 v3.5.8
功能列表 支持和聊天功能 Slack聊天完全同步 - 直接从Slack发送和接收用户信息。 立即工作 - 只需插入短码,即可立即安装和使用。 丰富的信息 - Dialogflow机器人发送丰富的信息。 机器人--集成一个由API.AI驱动的多语言机器人。 电子邮件通知 - 当收到回复时&#…...
2022年网络安全竞赛——数字取证调查attack.pcapng
攻击日志分析:需求环境可私信博主获取 任务环境说明: 服务器场景:PYsystem0031服务器场景操作系统:未知服务器场景FTP用户名:anonymous 密码:空从靶机服务器的FTP上下载attack.pcapng数据包文件,通过分析数据包attack.pcapng,找出黑客的IP地址,并将黑客的IP地址作为FL…...
2023最新MongoDB规范
前言 MongoDB是非关系型数据库的典型代表,DB-Engines Ranking 数据显示,近年来,MongoDB在 NoSQL领域一直独占鳌头。MongoDB是为快速开发互联网应用 而设计的数据库系统,其数据模型和持 久化策略就是为了构建高读/写的性能&#x…...
gcc的使用,调试工具gdb的使用
gcc编译 gcc编译可以分为四个步骤,预处理、编译、汇编、链接。 预处理命令:gcc -E hello.c -o hello.i编译命令:gcc -S hello.i -o hello.s汇编命令: gcc -c hello.s -o hello.o链接命令:gcc hello.o -o hello gcc…...
Python变量的定义和使用
定义:变量就是计算机内存中存储某些数据的位置的名称 形象理解变量就是一个存放东西的容器,该容器的名字就叫做变量,容器存放的东西就是变量的值 变量的组成: 标识:标识对象所储存的内存地址,使用内置函数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原理简析
屏幕渲染原理"现代计算机之父"冯诺依曼提出了计算机的体系结构: 计算机由运算器,存储器,控制器,输入设备和输出设备构成,每部分各司其职,它们之间通过控制信号进行交互。计算机发展到现在,已经出…...
第八届蓝桥杯省赛 C++ B组 - K 倍区间
✍个人博客:https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 📚专栏地址:蓝桥杯题解集合 📝原题地址:K 倍区间 📣专栏定位:为想参加蓝桥杯的小伙伴整理常考算法题解,祝大家…...
SVM实战:从线性可分到核技巧的全面解析
1. SVM入门:从分类问题到最优超平面 第一次听说SVM时,我正被一个简单的二分类问题困扰着。手头有一组客户数据,需要根据消费习惯将他们分成两类。试过逻辑回归,效果勉强及格;用决策树又容易过拟合。直到同事推荐了SVM&…...
ClickHouse连接避坑指南:Python开发者常遇到的5个问题及解决方案
ClickHouse连接避坑指南:Python开发者常遇到的5个问题及解决方案 当Python开发者初次尝试与ClickHouse建立连接时,往往会遇到各种意料之外的障碍。这些看似简单的连接问题,实际上可能隐藏着深层次的配置陷阱或性能瓶颈。本文将深入剖析五个最…...
faster-whisper-GUI架构设计与性能优化:构建高效语音识别工作流的技术实践
faster-whisper-GUI架构设计与性能优化:构建高效语音识别工作流的技术实践 【免费下载链接】faster-whisper-GUI faster_whisper GUI with PySide6 项目地址: https://gitcode.com/gh_mirrors/fa/faster-whisper-GUI 在语音识别技术快速发展的今天࿰…...
iperf3网络性能测试工具完全指南:从安装到企业级应用
iperf3网络性能测试工具完全指南:从安装到企业级应用 【免费下载链接】iperf3-win-builds iperf3 binaries for Windows. Benchmark your network limits. 项目地址: https://gitcode.com/gh_mirrors/ip/iperf3-win-builds 在当今数字化时代,网络…...
Maxwell Fields Calculator双模式切换指南:堆栈与代数表达式输入实战解析
Maxwell Fields Calculator双模式切换指南:堆栈与代数表达式输入实战解析 在电磁仿真领域,Maxwell Fields Calculator一直是工程师进行后处理分析的利器。随着2025 R1版本的推出,一项革命性的功能——双模式表达式输入,彻底改变了…...
智能处理与开源工具:突破传统背景抠图限制的实时解决方案
智能处理与开源工具:突破传统背景抠图限制的实时解决方案 【免费下载链接】obs-backgroundremoval An OBS plugin for removing background in portrait images (video), making it easy to replace the background when recording or streaming. 项目地址: https…...
FanControl完全指南:5分钟掌握Windows风扇智能控制
FanControl完全指南:5分钟掌握Windows风扇智能控制 【免费下载链接】FanControl.Releases This is the release repository for Fan Control, a highly customizable fan controlling software for Windows. 项目地址: https://gitcode.com/GitHub_Trending/fa/Fa…...
2026年,山东专业联想服务器解决方案,涵盖SR858 V3等众多型号!
在当今数字化飞速发展的时代,服务器作为企业数据处理和存储的核心设备,其性能和可靠性至关重要。联想服务器凭借其卓越的性能、丰富的功能和广泛的应用场景,成为众多企业的首选。今天,我们就来详细了解一下联想SR858 V3服务器。联…...
从零开始:在Unity中完美实现视频播放功能的完整指南(附常见报错解决方案)
从零开始:在Unity中完美实现视频播放功能的完整指南(附常见报错解决方案) 在游戏开发中,视频播放功能的应用场景越来越广泛——从开场动画、过场剧情到UI背景,视频元素能为玩家带来更丰富的视听体验。Unity作为主流的…...
思源宋体免费商用字体:设计师的终极开源字体解决方案
思源宋体免费商用字体:设计师的终极开源字体解决方案 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 还在为商业项目寻找高质量中文字体而烦恼吗?Source Han Se…...
