Java算法解析一:二分算法及其衍生出来的问题

这个算法的前提是,数组是升序排列的

算法描述:

i和j是指针可以表示查找范围

m为中间值

当目标值targat比m大时,设置查找范围在m右边:i =m-1

当目标值targat比m小时,设置查找范围在m左边:j =m+1

当targat的值等于m时,返回m的下标

如果最终没找到就返回-1;

算法实现:

public  int  birthDay(int[] a,int target){int i=0;int j=a.length-1;while(i<=j){int m= (i+j)/2;if(a[m]<target){//                目标值在右边i= m-1;} else if (target<a[m]) {//                目标值在左边j = m - 1;}else if (a[m] == target){//找到return m;}}return -1;
}public static void main(String[] args) {int targat=4;a1 a1= new  a1();int a[]= new int[]{2,4,6,8,9};int num=a1.birthDay(a,targat);System.out.println(num);
}

问题一:为什么循环条件是i<=j ,而不是i<j?

因为i 和 j 指向的元素也会参与比较,最后m可以和i和j重叠

问题二:(i+j)/2有没有问题?

在 Java 中,表达式 int a = (i + j) / 2 的结果是向下取整。整数除法会丢弃小数部分 。但是如果遇到非常大的数字呢?

Integer.MAX_VALUE2147483647,即 int 类型能够表示的最大值。

当第一次计算时:i + j 结果是 0 + 2147483647 = 2147483647

当第二次计算时:i = 1073741824j = 2147483647

i + j 结果是 1073741824 + 2147483647 = 3221225471

3221225471这个数字超过了整型能够表示的最大值,所以变成了负数:

public static void main(String[] args) {int i= 0;int j=Integer.MAX_VALUE;int m=(i+j)/2;System.out.println(m);System.out.println("————————————————————————————————————————————");i= m+1;  //结果在右边m= (i+j)/2;System.out.println(m);
}

所以我们可以用>>>移位运算符解决

>>>将二进制数的每一位向右移动一位,丢弃最右边的位,同时在最左边填充零。

使得结果变为正整数

2^7 ------> 2^6 就可以代替/2

例如:

1001 =9

移位后:

0100 = 4

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/402404.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数据结构第一天

数据结构基础知识 1.1 什么是数据结构 数据结构就是数据的逻辑结构以及存储操作 (类似数据的运算) 数据结构就教会你一件事&#xff1a;如何更有效的存储数据 1.2 数据 数据&#xff1a;不再是单纯的数字&#xff0c;而是类似于集合的概念。 数据元素&#xff1a;是数据的基本单…

使用 Python 进行 PDF 文件加密

使用 Python 解密加密的 PDF 文件-CSDN博客定义一个名为的函数&#xff0c;该函数接受三个参数&#xff1a;输入的加密 PDF 文件路径input_pdf、输出的解密 PDF 文件路径output_pdf和密码password。https://blog.csdn.net/qq_45519030/article/details/141256661 在数字化时代…

优先级队列的实现

什么是优先级队列 优先级队列是一种特殊的数据结构&#xff0c;它类似于队列或栈&#xff0c;但是每个元素都关联有一个优先级或权重。在优先级队列中&#xff0c;元素的出队顺序不是简单地按照它们进入队列的先后顺序&#xff08;先进先出&#xff0c;FIFO&#xff09;&#…

虚幻5|角色武器装备的数据库学习(不只是用来装备武器,甚至是角色切换也很可能用到)

虚幻5|在连招基础上&#xff0c;给角色添加武器并添加刀光|在攻击的时候添加武器并返回背后&#xff08;第一部分&#xff0c;下一部分讲刀光&#xff09;_unreal 如何给角色添加攻击-CSDN博客 目的&#xff1a;捡起各种不同的武器&#xff0c;捡起的武器跟装备的武器相匹配 …

练习:python条件语句、循环语句和函数的综合运用

需求描述&#xff1a; 期望输出效果&#xff1a; 练习成果&#xff1a; #简单的银行业务流程 many 50000 def main_menu():print("----------主菜单----------"f"\n{name}您好&#xff0c;欢迎来到ATM&#xff0c;请选择操作&#xff1a;""\n查询余…

挑战同档位最强护眼性能,书客L2 Pro革新护眼台灯全新体验!

2024年8月17日&#xff0c;SUKER书客在今日宣布&#xff1a;书客护眼台灯L2 PRO正式发售。书客作为专业护眼台灯实力老牌&#xff0c;主打“医学养护眼”的特性&#xff0c;是唯一做到降低96%近视风险的同时&#xff0c;缓解88%用眼疲劳&#xff0c;光源99.8%高度还原自然光&am…

Ubuntu离线安装docker

查看操作系统版本&#xff1a; rootzyh-VMware-Virtual-Platform:~/install# lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 24.04 LTS Release: 24.04 Codename: noble rootzyh-VMware-Virtual-Platform:~/install#…

删除镜像报子镜像依赖错误

1、删除镜像报子镜像依赖错误 出现这个错误的原因是因为有其他镜像依赖需要删除的镜像。 2解决方法 2.1首先查看无法删除的镜像被哪些镜像所依赖 docker image inspect --format{{.RepoTags}} {{.Id}} {{.Parent}} $(docker image ls -q --filter since${image_id}) # ${ima…

在阿里云上部署 Docker并通过 Docker 安装 Dify

目录 一、在服务器上安装docker和docker compose 1.1 首先关闭防火墙 1.2 安装docker依赖包 1.3 设置阿里云镜像源并安装docker-ce社区版 1.4 开启docker服务并设置开机自启动 1.5 查看docker版本信息 1.6 设置镜像加速 1.7 将docker compose环境复制到系统的bin目录下…

Jmeter接口测试断言详解

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 一、响应断言 对服务器的响应接口进行断言校验&#xff0c;来判断接口测试得到的接口返回值是否正确。 二、添加断言 1、apply to&#xff1a; 通常发出一个请…

可视化编程-七巧低代码入门02

1.1.什么是可视化编程 非可视化编程是一种直接在集成开发环境中&#xff08;IDE&#xff09;编写代码的编程方式&#xff0c;这种编程方式要求开发人员具备深入的编程知识&#xff0c;开发效率相对较低&#xff0c;代码维护难度较大&#xff0c;容易出现错误&#xff0c;也需要…

nginx核心配置示例

目录 1、nginx location的详细使用 &#xff08;1&#xff09;精确匹配 &#xff08;2&#xff09;区分大小写 &#xff08;3&#xff09;不区分大小写 &#xff08;4&#xff09;匹配文件名后缀 2、nginx下的用户认证 3、nginx自定义错误页面 4、自定义错误日志 5、n…

WordPress建站之头像及字体错误修正

目录 一、谷歌字体 二、头像网址 三、后续使用中的“坑” 网站建设好以后,会发现有些卡顿,网速好的环境感觉不明写,但是差的环境就难以忍受了。这是打开网页的控制台(Console)会发现有报错信息: 这些报错信息反应了2个问题: 谷歌字体网站无法访问头像网站无法访问下面…

基于Springboot 和Vue 的高校宿舍管理系统源码

网络上很多宿舍管理系统都不完整&#xff0c;大多数缺少数据库文件&#xff0c;所在使用极其不方便&#xff0c;由于本人程序员&#xff0c;根据代码&#xff0c;自己花时间不全了数据库文件&#xff0c;并且可以完美运行&#xff01;&#xff01;&#xff01;&#xff01;&…

基于VS2022+Qt5+C++的串口助手开发

目录 一、前言 二、环境准备 三、创建QT串口项目 ​编辑 四、串口项目实现 1.ui界面设计 2.添加QT串口模块 3.功能实现 ①串口扫描 ②波特率、停止位等设置 ③接收数据 ④发送数据 五、最终效果 六、总结 一、前言 如果有人之前看过我文章的话应该知道&#xf…

Hbase架构和读写流程

目录 1.概述 2.简介 3.Hbase架构 4.数据模型 5.Hbase写流程 6.Hbase读数据 1.概述 本篇文章将简单的讲述Hbase的架构和读写流程&#xff0c;多为理论部分&#xff0c;不涉及API代码 2.简介 从官方介绍可以知道,Hbase是一种分布式、可扩展、支持海量数据存储的 NoSQ…

Element-UI动态生成的表单元素验证示例

模拟数据 tableData: [{name: "系统1",score: 0,children:[{name: "一号子系统",score: 0,}]},{name: "系统2",score: 0,children:[{name: "3号子系统",score: 0,}]},{name: "系统3",score: 0,children:[{name: "5号子…

python-docx在word文件表格中指定行下插入新一行并填充值

from docx import Document from copy import deepcopydef insert_row_after_specific_value(doc, table_index, column_header, target_value, new_row_data):# 加载文档# doc doc_path# 检查表格索引是否有效if table_index > len(doc.tables):print("文档中没有足够…

matlab 音频音量处理(音量大小按照dB调节)

1 音量(声压级)以分贝(dB)表示的计算公式为: 2 % 已知的 x 值 x = 0:-1:-127; % 在这里填入 x 的具体值% 计算 y %y = 10

江理工文档管理系统的设计与实现

TOC springboot148江理工文档管理系统的设计与实现 绪论** 1.1 研究背景 在这个推荐个性化的时代&#xff0c;采用新技术开发一个文档系统来分享和展示内容是一个永恒不变的需求。本次设计的文档管理系统有管理员和用户两个角色。管理员功能有论坛管理&#xff0c;公告管理…