2018-05-08 69. Sqrt(x)

题意：给你一个数x，返回它的平方根，如果平方根是小数，向下取整。
解题思路：使用二分查找x的平方根ans，条件是不满足ans * ans > x，且满足(ans + 1) * (ans + 1) > x，此时ans为答案。
解题过程中要有两个防溢出操作：
1、条件判断时使用mid > x / mid;
2、求中间mid值使用mid = low + (high - low) / 2;

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