题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sqrtx 实现int sqrt(int x)函数。 计算并返回x的平方根，其中x是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2

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

解决思路：

题干关键： 求根，忽略小数部分 对于有序区间的搜索都可以考虑使用二分算法来加快对区间的搜索速度。 本例的目标是搜索到一个介于0到x之间的整数z使得z^2 <= x,并且没有一个整数y使得z^2<y^2<x。 说白了就是找一个最接进x的平方根并忽略掉小数部分。 在本例中假定下界是0，上界是x（1^2 = 1）。每次取折中，划分区间。 结束条件是下界与上界重合。将会满足折中点的平方小于等于x。 这样的算法的时间复杂度是log(n),空间复杂度是O(1). 在进行搜索区间缩小的时候特别要注意过滤掉折中搜索点，因为该点已经参与过计算，因此在下界上移的时候加一，上界下移的时候减一。

还有一些其他的解决方案，例如直接暴力搜索，从下界搜索到上界，这种的时间复杂度是x/2,其时间复杂度还是高于log(n)。 牛顿迭代法比二分快，但是目前的数学基础我看不懂

解决代码：

class Solution {
    public int mySqrt(int x) {
        int low = 0;
        int high = x;
        int ans  = -1;
        while (low <= high) {
            int mid = low+(high-low)/2;
            // 判断结果
            long  result = (long)mid * mid;
            if(result <= x){
                ans = mid;
                low = mid + 1;
            } else {
                high = mid -1;
            }
        }
        return ans;
    }
}