题解 | #求平方根#

方法：二分查找 本题是二分查找算法的典型应用场景：查找一个有确定范围的整数，可以根据 单调性 逐渐缩小搜索范围； 单调性：注意到题目中给出的「例 2」，8 的平方根返回 2，不可以返回 3。因此：如果一个数 a 的平方大于 x ，那么 a 一定不是 x 的平方根，下一轮需要在区间 [0..a - 1] 里继续查找 x 的平方根。

public class Solution {
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    public int mysqrt (int x) {
        // write code here
        if(x == 0){
            return 0;
        }
        if(x == 1){
            return 1;
        }
        int left =1;
        int right = x/2;
        while(left<right){
            int mid = left + (right - left+1)/2;
            if(mid>x/mid){
                right = mid -1;
            }else{
                left = mid;
            }
        }
        return left;
    }
}