changgyhub / leetcode_101

LeetCode 101:力扣刷题指南
8.57k stars 1.16k forks source link

二分法求开方的算法过程中存在问题 #64

Closed View0 closed 1 month ago

View0 commented 2 years ago

class Solution { public: int mySqrt(int x) { if(x == 0) return x; int left = 1, right = x; int mid, sqrt; while(left <= right) { mid = left + (right - 1) / 2; sqrt = x / mid; if(sqrt == mid) return sqrt; if(sqrt > mid) left = mid + 1; else right = mid - 1; } return left; } }; 当x输入为8时: 第1次判断left = 1,right = 8,进入循环后mid = 4,sqrt = 2,right = 3; 第2次判断left = 1,right = 3,进入循环后mid = 2,sqrt = 4,left = 3; 第3次判断left = 3,right = 3,进入循环后mid = 4,sqrt = 2,right = 3; 之后循环会一直进行下去,出现死循环。

LS-King commented 2 years ago

循环内对mid变量的赋值语句写错了

class Solution { public: int mySqrt(int x) { if(x == 0) return x; int left = 1, right = x; int mid, sqrt; while(left <= right) { mid = left + (right - left) / 2; //这句你的源代码中错写为了1,而在电子书中写的是小写的英文字母l sqrt = x / mid; if(sqrt == mid) return sqrt; if(sqrt > mid) left = mid + 1; else right = mid - 1; } return left; } };

View0 commented 2 years ago

不是呀,我写的是left和right变量,你的是l和r变量,我源代码中的left就是你源代码的l不是么?然后你拿你那个程序手写演算下输入a = 8的情况,我感觉是个死循环。谢谢哈,我昨晚上才看到,回复的有点晚不好意思。

------------------ 原始邮件 ------------------ 发件人: "changgyhub/leetcode_101" @.>; 发送时间: 2022年3月27日(星期天) 下午5:37 @.>; 抄送: "张泽啸 @.**@.>; 主题: Re: [changgyhub/leetcode_101] 二分法求开方的算法过程中存在问题 (Issue #64)

循环内对mid变量的赋值语句写错了

class Solution { public: int mySqrt(int x) { if(x == 0) return x; int left = 1, right = x; int mid, sqrt; while(left <= right) { mid = left + (right - left) / 2; //这句你的源代码中错写为了1,而在电子书中写的是小写的英文字母l sqrt = x / mid; if(sqrt == mid) return sqrt; if(sqrt > mid) left = mid + 1; else right = mid - 1; } return left; } };

— Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you authored the thread.Message ID: @.***>

changgyhub commented 2 years ago
int mySqrt(int a) {
    if (a == 0) return a;
    int l = 1, r = a, mid, sqrt;
    while (l <= r) {
        mid = l + (r - l) / 2;
        sqrt = a / mid;
        if (sqrt == mid) {
            return mid;
        } else if (mid > sqrt) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return r;
}

这是书里的源代码,我在leetcode是能跑通a = 8的,不如你再试试?