面试算法72：求平方根

题目

输入一个非负整数，请计算它的平方根。正数的平方根有两个，只输出其中的正数平方根。如果平方根不是整数，那么只需要输出它的整数部分。例如，如果输入4则输出2；如果输入18则输出4。

分析

整数n的平方根一定小于或等于n。同时，除0之外的所有整数的平方根都大于或等于1。因此，整数n的平方根一定在从1到n的范围内，取这个范围内的中间数字m，并判断m²是否小于或等于n。如果m²≤n，那么接着判断(m+1)²是否大于n。如果满足(m+1)²>n，那么m就是n的平方根。

解

public class Test {
    public static void main(String[] args) {
        System.out.println(mySqrt(18));
    }

    public static int mySqrt(int n) {
        int left = 1;
        int right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (mid <= n / mid) {
                if ((mid + 1) > n / (mid + 1)) {
                    return mid;
                }

                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }

        return 0;
    }
}