一个数的平方根肯定不会大于这个数的一半，利用这个性质来做二分：

• 设置左右边界：从1到这个数本身；
• 若mid的平方小于x，且mid + 1的平方大于x，则mid就是x的平方根，根据这一点来终止二分查找。

class Solution {
public:
    int mySqrt(int x) {
        int left = 1, right = x;    //除了0以外，所有数的平方根都在1到它本身之间

        while (left <= right)
        {
            //相当于mid = (left + right) / 2，但这么写会爆int
            int mid = left + ((right - left) >> 1);
            if (mid <= x /mid)
            {
                if ((mid + 1) > x / (mid + 1)) return mid;
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }

        return 0;                   //0的平方根是0
    }
};