代码编织梦想

题目:
69. x 的平方根
实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

来源:力扣(LeetCode)

分析:
题目很简单,很容易就想到使用二分查找。
答案区间为 [left, right], 并且 mid = (left + right) >>>1
更新条件为:
if(mid * mid > x) right = mid - 1;
else left = mid;

上面的写法逻辑是正确的,但是会出现死循环的现象:当 (left + right) >>>1 与 left 相等时。
这时,其实就无法在缩小区间了。

而造成这种情况的原因是因为区间的大小为2了
[left, right] 满足 left + 1 == right ,所以一定满足 mid = (left + right) / 2 = (left + left + 1) / 2 = left

所以造成死循环的根本原因是使用了 : left = mid;这条语句!!!

我们在写二分查找时,只要避免了这条语句,就可以避免死循环了。

当更新条件需要 left = mid时,我们可以直接去判断 mid + 1的情况,
让更新变为 left = mid + 1,这样就不会在出现死循环了。

代码:

class Solution {
    public int mySqrt(int x) {
        int i = 0, j = (int)Math.sqrt(Integer.MAX_VALUE), mid, t;
        while(i < j) {
            mid = (i+j)>>>1;
            t = mid * mid;
            if(t == x) return mid;
            else if(t > x) j = mid - 1;
            //else i = mid; 会造成死循环
            else if((mid+1)*(mid+1) > x) return mid;
            else i = mid+1;
            
        }
        return i;
    }
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/STILLxjy/article/details/110821165

LeetCode题解(0302):包含全部黑色像素的最小矩形(Python)-爱代码爱编程

题目:原题链接(困难) 标签:广度优先搜索、深度优先搜索、二分查找 解法时间复杂度空间复杂度执行用时Ans 1 (Python) O (

Leetcode[二分查找] 50. Pow(x, n)-爱代码爱编程

Leetcode[二分查找] 50. Pow(x, n) 审题代码实现反思 审题 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 示例 1: 输入: 2.00000, 10 输出: 1024.00000 示例 2: 输入: 2.10000, 3 输出: 9.26100 示例 3: 输入: 2.00000, -2 输出: 0.

第一个错误的版本-爱代码爱编程

第一个错误的版本 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version

Java二分法查找(递归、循环实现)-爱代码爱编程

public class BinarySearch { /** * @author JadeXu * @// TODO: 2020/12/7 二分查找 * 思路: * 1、获取数组的中间值,先获取下标,方便多次查找 * 奇数位的数组直接获取中间位,偶数位的数组获取中间的第一位或第二位都可,一般获取第

Leetcode[二分查找] 74. 搜索二维矩阵-爱代码爱编程

Leetcode[二分查找] 74. 搜索二维矩阵 审题代码实现反思 审题 编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性: 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。 示例 1: 输入:matrix = [[1,3,5,7],[10,11,16,20],[23,3

LeetCode题解:704.二分查找-爱代码爱编程

二分查找(easy) 更好的阅读体验应该是: 审题-思考答题整理-归纳 一、题目 LeetCode:704.二分查找 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示例: 输入: nums = [-1,0,3,

纯干货:死循环线程居然不执行了?-爱代码爱编程

最近弄了一个新的应用,专门用来收集一些应用数据作参考以及问题排查定位的,但是上线一段时间之后出现了一个非常非常诡异的问题。 问题描述 收集器采用异步化,启用了一个独立的线程专门收集各个服务发送过来的数据进行消费。刚开始上线的时候数据能够按时进来,但是一个诡异的事情发生了,每隔一段时间该线程不消费了。 这是大概代码: while (true) {

多线程下的HashMap死循环问题详解-爱代码爱编程

小伙伴们大家好呀,今天看技术博文的时候看到一个很有意思的问题,就如标题所示------》在多线程的情况下关于HashMap的死循环问题,还记我在刚学JavaSE时候,看到过这个问题,当时的知识储备不够,没有深究,今天来详细说一说,希望能帮到你们,一起进步。 正文开始: Java的HashMap是非线程安全的。多线程下应该用ConcurrentHashM

HashMap多线程不安全原因分析-爱代码爱编程

众所周知,HashMap在多线程环境下是线程不安全的, 在jdk1.7中,主要有两个方面线程不安全,一是多线程扩容因为头插法容易造成死循环。二是put的时候容易造成数据覆盖。 在jdk1.8中,使用尾插法避免了resize时死循环,但是put的时候,多线程环境下仍然会出现数据覆盖的问题。 接下来逐个分析问题点: jdk1.7中扩容死循环的问题 H