当前位置: 首页 > 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;祝大家…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

【Linux系统】Linux环境变量:系统配置的隐形指挥官

。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量&#xff1a;setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...

Mysql故障排插与环境优化

前置知识点 最上层是一些客户端和连接服务&#xff0c;包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念&#xff0c;为通过安全认证接入的客户端提供线程。同样在该层上可…...

CTF show 数学不及格

拿到题目先查一下壳&#xff0c;看一下信息 发现是一个ELF文件&#xff0c;64位的 ​ 用IDA Pro 64 打开这个文件 ​ 然后点击F5进行伪代码转换 可以看到有五个if判断&#xff0c;第一个argc ! 5这个判断并没有起太大作用&#xff0c;主要是下面四个if判断 ​ 根据题目…...

java+webstock

maven依赖 <dependency><groupId>org.java-websocket</groupId><artifactId>Java-WebSocket</artifactId><version>1.3.5</version></dependency><dependency><groupId>org.apache.tomcat.websocket</groupId&…...