二分查找 P15 第一种方法

ritchiesama commented 3 years ago

作者你好, 首先非常感谢您分享的letcode101,让我获益匪浅. 但是其中有一个解让我不是很明白,希望指点一下, 关于二分查找 P15 第一种方法, 我有些疑问实际上如果a = 8的时候, while是个死循环, 因为此时mid = 4, 无论 right-1或者left-1 都是3, 然鹅

  mid = left + (right - 1) / 2;

让下一个mid又是4...如此循环往复.....	次数	right	left	mid
1	1	8	4	0
2	1	3	2	2
3	3	3	4	4
4	3	3	4	2
5	3	3	4	2

...

我的代码如下

class Solution {
    public int mySqrt(int a) {
        if(a == 0) return a;
        int left = 1, right = a, mid, sqrt;
        while(left <= right){
            mid = left + (right - 1) / 2;
            sqrt = a / mid;
            if(sqrt == mid){
                return mid;
            }else if(mid > sqrt){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return right;
    }

希望大佬指点一下我哪里做错了...非常感谢!!!

jihchi commented 3 years ago

Hi @ritchiesama

It is l (lowercase of L) not 1 on the book.

-mid = left + (right - 1) / 2;
+mid = left + (right - left) / 2;

Edit: modified code to adapt your example

ritchiesama commented 3 years ago

Oh, I got it! I must blind. Thank you for the explanation.

Best, Qi

在 2021-04-14 20:23:15，"Jihchi Lee" @.***> 写道：

Hi @ritchiesama

It should be l (lowercase of L) not 1

-mid = left + (right - 1) / 2;+mid = left + (right - l) / 2;

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or unsubscribe.

changgyhub commented 3 years ago

Thanks for volunteering, @jihchi. I will add you to the acknowledgments.

changgyhub / leetcode_101

二分查找 P15 第一种方法 #34