[数据结构与算法]69. x 的平方根

69. x 的平方根：

题目链接 ：69. x 的平方根

题目：给你一个非负整数 x ，计算并返回 x 的 平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

思路：

1、二分法的数学呈现，需要注意细节。
2、对于x为0和1，需要特殊处理。
3、mid=left+(right-left+1)/2是强制向上取整，防止区间内左右边界相等产生死循环。
4、使用除法验证平方根，防止乘法导致样例过大数据越界。
5、 要考虑判断target大于最大值，直接加入数组，数组扩容的情况。

AC代码：

class Solution {
    public int mySqrt(int x) {
        if(x==0){
            return 0;
        }
        if(x==1)
        {
            return 1;
        }
        int left=1;
        int right=x/2;
        while(left<right)
        {
 //防止只有两个数的时候，向下取整，导致mid = left，区间内产生死循环
            int mid=left+(right-left+1)/2;
            if(mid>x/mid)
            {
                right=mid-1;
            }
            else{
                left=mid;
            }
        }
        return left;
       
    }
}