题目描述

实现int sqrt(int x)函数。

计算并返回x的平方根，其中x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

样例

样例一

输入: 4
输出: 2

样例二

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

算法1

(二分) $O(logn)$

二分出最大的 y，满足 y2≤x。
则 y 就是答案。

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int mySqrt(int x) {
        long l = 0, h = (long)x + 1;
        while(l < h){
            long m = (l + h) / 2;
            if(m * m > x) h = m; else l = ++m;
        }
        return (int)l - 1;
    }
};