当前位置: 首页 > 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: 然后呢,去懒加载这个数组, 然后呢,接下来啊,走这一句话, 第一次…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

前端中slice和splic的区别

1. slice slice 用于从数组中提取一部分元素&#xff0c;返回一个新的数组。 特点&#xff1a; 不修改原数组&#xff1a;slice 不会改变原数组&#xff0c;而是返回一个新的数组。提取数组的部分&#xff1a;slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...