二分查找。小心溢出。

class Solution {
public:
  int mySqrt(int x) {
    if (x <= 1) {
      return x;
    }
    // i means the first number that greater than sqrt x
    uint64_t i = 1;
    while (true) {
      uint64_t square = i * i;
      if (square == x) {
        return i;
      }
      if (square > x) {
        break;
      }
      i *= 2;
    }
    uint64_t l = i / 2 - 1;
    uint64_t r = i;
    while (l + 1 != r) {
      uint64_t mid = l + (r - l) / 2;
      uint64_t square = mid * mid;
      if (square <= x) {
        l = mid;
      } else {
        r = mid;
      }
    }
    return l;
  }
};