Leetcode#69 Sqrt(x)

原题地址

小心溢出。

检测乘法溢出的方法：设乘数为A、B，乘积为C，检验C / A =? B，前提是B != 0

检测加法溢出的方法：检验A + B <? 0

代码：

int sqrt(int x) {
  int l = 0;
  int r = x;

  while (l <= r) {
    int m = l + (r - l) / 2;
    int p = m * m;
    bool overflow = m != 0 && p / m != m;
    if (p == x)
      return m;
    else if (!overflow && p < x)
      l = m + 1;
    else
      r = m - 1;
  }

  return min(l, r);
}