求算术平方根

leetcode 69题
求x的算术平方根。例如4的算术平方根是2。 8的算术平方根也是2（取整）。9的算术平方根是3。

注意的点

• 使用二分查找法，（递归和while循环）
• 二分查找是先比较mid与目标值的大小，而不是先比较两端left和right。
• 节省内存：少新建变量
• 节省内存：用窄类型，例如用byte替换int。
• 减少执行用时：优化算法。

递归实现

public class Test {
    public static void main(String[] args) {
        System.out.println(mySqrt(2));
        System.out.println(mySqrt(3));
        int x = 2147483647;
        System.out.println(mySqrt(x));
    }

    public static int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }
        return count(1, x, x);
    }

    public static int count(int left, int right, int x) {
//      System.out.println("start:" + left + " " + right);
        int mid = left + (right - left) / 2; //防止（left+right)溢出

        if (mid == x / mid) {//防止溢出用除法
            return mid;
        } else if (mid < x / mid) {//mid*mid<x
            if ((mid + 1) > x / (mid + 1)) { //(mid+1)*(mid+1)>x
                return mid;
            } else {
                return count(mid + 1, right, x);
            }
        } else if (mid > x / mid) {//mid*mid>x
            return count(left, mid - 1, x);
        }
        System.out.println("error");
        return -1;
    }

}

while循环实现

public class Test2 {
    public static void main(String[] args) {
        System.out.println(mySqrt(2));
        System.out.println(mySqrt(8));
//        System.out.println(mySqrt(2147483647));

    }

    public static int mySqrt(int x) {
        // 特殊值判断
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }

        int left = 1;
        int right = x;
        // 在区间 [left..right] 查找目标元素
        while (left <= right) {
            int mid = left + (right - left) / 2;
//            System.out.println("开始：left:" + left + " right:" + right + " mid:" + mid);
            if (mid > x / mid) { // 注意：这里为了避免乘法溢出，改用除法
                right = mid - 1; // 下一轮搜索区间是 [left..mid - 1]
            } else if (mid == x / mid) {
                return mid;
            } else {
                // 下一轮搜索区间是 [mid+1..right]
                left = mid + 1;
            }
//            System.out.println("结束：left:" + left + " right:" + right);
        }
        return left - 1;
    }

}