69.x的平方根

题目描述

链接: https://leetcode-cn.com/problems/sqrtx/
这个题目说的是，你要实现一个函数，来计算非负整数 n 的平方根，平方根只需返回整数部分即可。

比如，使用你实现的函数来计算 9 的平方根是 3：

f(9) = 3

由于 8 的平方根是 2 点几，使用你实现的函数只需要返回整数部分 2 即可：

f(8) = 2

解题思路:

使用 二分法, 使得平方无限逼近答案.
这里没用Long, 答案溢出了, 需要用Long防止进行平方的时候溢出.

代码:

class Solution {
    public int mySqrt(int x) {
        long low = 0, high = x;
        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (mid * mid > x) {
                high = mid - 1;
            } else if (mid * mid < x) {
                low = mid + 1;
            } else {
                return (int) mid;
            }
        }
        return (int) high;
    }
}