二分查找的实现代码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 倍区间 📣专栏定位:为想参加蓝桥杯的小伙伴整理常考算法题解,祝大家…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
python执行测试用例,allure报乱码且未成功生成报告
allure执行测试用例时显示乱码:‘allure’ �����ڲ����ⲿ���Ҳ���ǿ�&am…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...
【实施指南】Android客户端HTTPS双向认证实施指南
🔐 一、所需准备材料 证书文件(6类核心文件) 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...
【iOS】 Block再学习
iOS Block再学习 文章目录 iOS Block再学习前言Block的三种类型__ NSGlobalBlock____ NSMallocBlock____ NSStackBlock__小结 Block底层分析Block的结构捕获自由变量捕获全局(静态)变量捕获静态变量__block修饰符forwarding指针 Block的copy时机block作为函数返回值将block赋给…...
鸿蒙Navigation路由导航-基本使用介绍
1. Navigation介绍 Navigation组件是路由导航的根视图容器,一般作为Page页面的根容器使用,其内部默认包含了标题栏、内容区和工具栏,其中内容区默认首页显示导航内容(Navigation的子组件)或非首页显示(Nav…...
