欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode69

程序员文章站 2022-03-19 11:57:14
...

使用二分查找求小于某个数字的平方根的最大整数

思路:使用二分查找减少查找时间,要每次记录mid的值,否则left和right可能会大于或者小于真正的结果值

leetcode69

class Solution {
    public int mySqrt(int x) {
        if(x == 0||x == 1) return x;
        int left = 1,right = x,res = -1;
        
        while(left <= right) {
            int mid = left + (right - left)/2;
            if((long) mid*mid <= x) {
                res = mid;
                //找到了一个可能解,小于x的都是可能的情况
                //但需要找到可能情况中的最大值,而left记录
                //的可能比最大值要大,因此,要记录每次的mid
                left = mid + 1;
            }
            else
                right = mid - 1;
        }

        return res;
    }
}

 

相关标签: 刷题 java