首页 > itarticle > [leetcode]sqrt(x)

[leetcode]sqrt(x)

admin 11月 11, 2020 0

题目描述

Implement int sqrt(int x).

Compute and return the square root of x.

代码

使用二分搜索，方法简单写对也不容易啊:)

public class Solution{
    
	public int (int x) {
        if(x == 0) return 0;
        
        int left = 1, right = x;
        while(true){
            int mid = left + (right - left)/2;
            //除法能防止溢出，mid*mid>x会溢出
            if (mid > x/mid) {
                right = mid - 1;
            } else {
                //除法是有取整的，需要注意
                if (mid + 1 > x/(mid + 1))
                    return mid;
                left = mid + 1;
            }
        }
    }
}

另一种写法

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