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

2024-05-10 03:28

本文主要是介绍二分查找向下取整导致的死循环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 的平方根的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域(Scope)和标识符查找(IdentifierLookup)是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找(Ordinary Lookup)2. 限定查找(Qualif

MySQL版本问题导致项目无法启动问题的解决方案

《MySQL版本问题导致项目无法启动问题的解决方案》本文记录了一次因MySQL版本不一致导致项目启动失败的经历,详细解析了连接错误的原因,并提供了两种解决方案:调整连接字符串禁用SSL或统一MySQL... 目录本地项目启动报错报错原因:解决方案第一个:第二种:容器启动mysql的坑两种修改时区的方法:本地

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

C#实现查找并删除PDF中的空白页面

《C#实现查找并删除PDF中的空白页面》PDF文件中的空白页并不少见,因为它们有可能是作者有意留下的,也有可能是在处理文档时不小心添加的,下面我们来看看如何使用Spire.PDFfor.NET通过C#... 目录安装 Spire.PDF for .NETC# 查找并删除 PDF 文档中的空白页C# 添加与删

python中的整除向下取整的操作方法

《python中的整除向下取整的操作方法》Python中的//是整数除法运算符,用于执行向下取整的除法,返回商的整数部分,不会四舍五入,它在分治法、索引计算和整数运算中非常有用,本文给大家介绍pyth... 目录1. // 的基本用法2. // vs /(普通除法)3. // 在 mid = len(lis

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中常用的四种取整方式分享

《Python中常用的四种取整方式分享》在数据处理和数值计算中,取整操作是非常常见的需求,Python提供了多种取整方式,本文为大家整理了四种常用的方法,希望对大家有所帮助... 目录引言向零取整(Truncate)向下取整(Floor)向上取整(Ceil)四舍五入(Round)四种取整方式的对比综合示例应

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que