力扣69. x 的平方根

二分查找

• 思路：
  • 设置 left 指针为 0，right 指针为 x；
  • 如果 mid = (right - left) / 2 + left 的平方小于或等于 x，此时移动 left = mid + 1，并缓存当前 mid 值，可能这个 mid 就是结果，或者 x 的平方根有更大的数；
  • 否则移动 right 到 mid -1，因为 mid^2 > x，x 的平方根比 mid 小；
  • 直到找到 mid 的值；

class Solution {
public:
    int mySqrt(int x) {
        int left = 0;
        int right = x;
        int result = -1;

        while (left <= right) {
            int mid = (right - left) / 2 + left;
            if ((long long) mid * mid <= x) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return result;
    }
};