当前位置: 首页 > news >正文

二分查找向下取整导致的死循环69. x 的平方根

二分查找向下取整导致的死循环

        考虑伪题目:从数组arr中查找出目标元素target对应的下标,如果数组中不存在目标元素,找

到第一个元素值小于target的元素的下标。

        编写二分查找算法如下:

    @Testvoid testBinarySearch(){int[] arr = new int[]{1, 2};int left = 0, right = arr.length - 1, target = 2;while(left < right){int mid = left + (right - left) / 2;if(arr[mid] == target){System.out.println("Find target index is :" + mid);}else if(arr[mid] > target){right = mid + 1;}else if(arr[mid] < target){left = mid;}System.out.println("Program is running...");}}

        通过代码执行结果可以得出此二分查找陷入死循环:

        分析以上二分查找代码逻辑,题目意思可以理解为寻找第一个小于或者等于target目标元素的下标。当只有两个元素的时候,此时情况[left, right]由于Java是向下取值,此时right和left仅仅相隔一个元素,计算mid相当于(left + left + 1)/ 2等于left,mid对应left位置,由于arr[mid] < target,所以left取值为mid,也就是[left,right]的相对位置保持不变,所以陷入死循环。

        解决方案,将向下取整变为向上取整,完美解决,修改后代码如下:

在二分查找中【只有两个元素时】出现死循环,如下:

[left,right]==>取值策略:left = mid,right = mid - 1,此时只有进入right循环时才会改变left、right的相对位置,否则进入left = mid死循环。

解决方案:将mid计算方案中向下取整改为向上取值,此时只有两个元素的时候永远计算的是较大者。【要针对具体情况讨论

 69. x 的平方根 

        题目链接:69. x 的平方根 - 力扣(LeetCode)

        上面的问题的引入以及解答均是自己在做lc题目69的时候看到的题解中某句话的理解。

 参考链接

69. x 的平方根 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/sqrtx/solutions/7866/er-fen-cha-zhao-niu-dun-fa-python-dai-ma-by-liweiw/?envType=study-plan-v2&envId=top-interview-150

相关文章:

二分查找向下取整导致的死循环69. x 的平方根

二分查找向下取整导致的死循环 考虑伪题目&#xff1a;从数组arr中查找出目标元素target对应的下标&#xff0c;如果数组中不存在目标元素&#xff0c;找 到第一个元素值小于target的元素的下标。 编写二分查找算法如下&#xff1a; Testvoid testBinarySearch(){int[] arr n…...

Kivy 异步任务

如果要进行一些非常耗时的操作(例如&#xff1a;爬虫等)&#xff0c;那么页面就会在这里卡住&#xff0c;而系统就会以为这个软件无响应&#xff0c;并提示关闭&#xff0c;可以说明用户体验极差&#xff0c;因此我们在此处引入异步操作。 在py中引入事件调节器&#xff0c;并在…...

DEV--C++小游戏(吃星星(0.1))

目录 吃星星&#xff08;0.1&#xff09; 简介 头文件 命名空间变量 副函数 清屏函数 打印地图函数 移动函数 主函数 0.1版完整代码 吃星星&#xff08;0.1&#xff09; 注&#xff1a;版本<1为未实现或只实现部分 简介 用wasd去吃‘*’ 头文件 #include<bi…...

LINUX 入门 4

LINUX 入门 4 day6 7 20240429 20240504 耗时&#xff1a;240min 课程链接地址 第4章 LINUX环境编程——实现线程池 C基础 第3节 #define里面的行不能乱空行&#xff0c;要换行就打\ typedef 是 C 和 C 中的一个关键字&#xff0c;用于为已有的数据类型定义一个新的名字。…...

Imagine Flash、StyleMamba 、FlexControl、Multi-Scene T2V、TexControl

本文首发于公众号&#xff1a;机器感知 Imagine Flash、StyleMamba 、FlexControl、Multi-Scene T2V、TexControl You Only Cache Once: Decoder-Decoder Architectures for Language Models We introduce a decoder-decoder architecture, YOCO, for large language models, …...

Java Collections.emptyList() 方法详解

前言 在Java开发的日常中&#xff0c;我们常常需要处理集合数据结构&#xff0c;而这其中就免不了要面对“空集合”的场景。传统的做法可能是直接返回 null&#xff0c;但这往往会引入空指针异常的风险&#xff0c;降低了代码的健壮性。幸运的是&#xff0c;Java为我们提供了一…...

Vue前端环境准备

vue-cli Vue-cli是Vue官方提供的脚手架&#xff0c;用于快速生成一个Vue项目模板 提供功能&#xff1a; 统一的目录结构 本地调试 热部署 单元测试 集成打包上线 依赖环境&#xff1a;NodeJs 安装NodeJs与Vue-Cli 1、安装nodejs&#xff08;已经安装就不用了&#xff09; node-…...

代码随想录算法训练营第四十二天| 01背包问题(二维、一维)、416.分割等和子集

系列文章目录 目录 系列文章目录动态规划&#xff1a;01背包理论基础①二维数组②一维数组&#xff08;滚动数组&#xff09; 416. 分割等和子集①回溯法&#xff08;超时&#xff09;②动态规划&#xff08;01背包&#xff09;未剪枝版剪枝版 动态规划&#xff1a;01背包理论基…...

故障——蓝桥杯十三届2022国赛大学B组真题

问题分析 这道题纯数学&#xff0c;考察贝叶斯公式 AC_Code #include <bits/stdc.h> using namespace std; typedef pair<int,double> PI; bool cmp(PI a,PI b){if(a.second!b.second)return a.second>b.second;return a.first<b.first; } int main() {i…...

SSD存储基本知识

存储技术随着时间的推移经历了显著变化&#xff0c;新兴的存储介质正逐步挑战已经成为行业标准的硬盘驱动器&#xff08;HDD&#xff09;。在众多竞争者中&#xff0c;固态硬盘&#xff08;SSD&#xff09;是最广泛采用且最有潜力占据主导地位的——它们速度快、运行安静&#…...

buuctf-misc题目练习二

ningen 打开题目后是一张图片&#xff0c;放进winhex里面 发现PK&#xff0c;PK是压缩包ZIP 文件的文件头&#xff0c;下一步是想办法进行分离 Foremost可以依据文件内的文件头和文件尾对一个文件进行分离&#xff0c;或者识别当前的文件是什么文件。比如拓展名被删除、被附加…...

Nginx rewrite项目练习

Nginx rewrite练习 1、访问ip/xcz&#xff0c;返回400状态码&#xff0c;要求用rewrite匹配/xcz a、访问/xcz返回400 b、访问/hello时正常访问xcz.html页面server {listen 192.168.99.137:80;server_name 192.168.99.137;charset utf-8;root /var/www/html;location / {root …...

2024,AI手机“元年”? | 最新快讯

文 | 伯虎财经&#xff0c;作者 | 铁观音 2024年&#xff0c;小米、荣耀、vivo、一加、努比亚等品牌的AI手机新品如雨后春笋般涌现。因此&#xff0c;这一年也被业界广泛视为AI手机的“元年” 试想&#xff0c;当你轻触屏幕&#xff0c;你的手机不仅响应你的指令&#xff0c;更…...

5月9(信息差)

&#x1f30d; 可再生能源发电量首次占全球电力供应的三成 &#x1f384;马斯克脑机接口公司 Neuralink 计划将 Link 功能扩展至现实世界&#xff0c;实现控制机械臂、轮椅等 马斯克脑机接口公司 Neuralink 计划将 Link 功能扩展至现实世界&#xff0c;实现控制机械臂、轮椅等…...

leetcode203-Remove Linked List Elements

题目 给你一个链表的头节点 head 和一个整数 val &#xff0c;请你删除链表中所有满足 Node.val val 的节点&#xff0c;并返回 新的头节点 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,6,3,4,5,6], val 6 输出&#xff1a;[1,2,3,4,5] 示例 2&#xff1a; 输入&…...

2024付费进群系统,源码及搭建变现视频课程(教程+源码)

自从我做资源站项目盈利稳定后&#xff0c;我越来越对网站类项目感兴趣了&#xff0c;毕竟很多网站类项目还是需要一定技术门槛的&#xff0c;可以过滤掉一些人&#xff0c;很多新人做项目就只盯着短视频&#xff0c;所以网站类项目也就没那么的卷。 这个付费进群系统&#xf…...

深入理解Django:中间件与信号处理的艺术

title: 深入理解Django&#xff1a;中间件与信号处理的艺术 date: 2024/5/9 18:41:21 updated: 2024/5/9 18:41:21 categories: 后端开发 tags: Django中间件信号异步性能缓存多语言 引言 在当今的Web开发领域&#xff0c;Django以其强大的功能、简洁的代码结构和高度的可扩…...

rk3588局域网推流

最近无意间看见在网上有使用MediaMtx插件配合ffmpeg在Windows来进行推流&#xff0c;然后在使用其他软件进行拉流显示数据图像的&#xff0c;既然windows都可以使用 &#xff0c;我想linux应该也可以&#xff0c;正好手上也有一块RK3588的开发板&#xff0c;就测试了一下&#…...

Android虚拟机机制

目录 一、Android 虚拟机 dalvik/art&#xff08;6版本后&#xff09;二、Android dex、odex、oat、vdex、art区别 一、Android 虚拟机 dalvik/art&#xff08;6版本后&#xff09; 每个应用都在其自己的进程中运行&#xff0c;都有自己的虚拟机实例。ART通过执行DEX文件可在设…...

【触摸案例-手势解锁案例-按钮高亮 Objective-C语言】

一、我们来说这个self.btns,这个问题啊,为什么不用_btns, 1.我们说,在懒加载里边儿,经常是写下划线啊,_btns,为什么不写,首先啊,这个layoutSubviews:我们第一次,肯定会去执行这个layoutSubviews: 然后呢,去懒加载这个数组, 然后呢,接下来啊,走这一句话, 第一次…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

给网站添加live2d看板娘

给网站添加live2d看板娘 参考文献&#xff1a; stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下&#xff0c;文章也主…...