二分查找的实现代码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 倍区间 📣专栏定位:为想参加蓝桥杯的小伙伴整理常考算法题解,祝大家…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案
在移动互联网营销竞争白热化的当下,推客小程序系统凭借其裂变传播、精准营销等特性,成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径,助力开发者打造具有市场竞争力的营销工具。 一、系统核心功能架构&…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
[USACO23FEB] Bakery S
题目描述 Bessie 开了一家面包店! 在她的面包店里,Bessie 有一个烤箱,可以在 t C t_C tC 的时间内生产一块饼干或在 t M t_M tM 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC,tM≤109)。由于空间…...
从实验室到产业:IndexTTS 在六大核心场景的落地实践
一、内容创作:重构数字内容生产范式 在短视频创作领域,IndexTTS 的语音克隆技术彻底改变了配音流程。B 站 UP 主通过 5 秒参考音频即可克隆出郭老师音色,生成的 “各位吴彦祖们大家好” 语音相似度达 97%,单条视频播放量突破百万…...
Python的__call__ 方法
在 Python 中,__call__ 是一个特殊的魔术方法(magic method),它允许一个类的实例像函数一样被调用。当你在一个对象后面加上 () 并执行时(例如 obj()),Python 会自动调用该对象的 __call__ 方法…...
CMS内容管理系统的设计与实现:多站点模式的实现
在一套内容管理系统中,其实有很多站点,比如企业门户网站,产品手册,知识帮助手册等,因此会需要多个站点,甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...
