Pengjielee's blog

题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:  
输入: 4
输出: 2

示例 2:  
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sqrtx 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

由于 x 平方根的整数部分ans 是满足 k^2 <= x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。

二分查找的下界为 0，上界可以粗略地设定为 x。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/sqrtx/solution/x-de-ping-fang-gen-by-leetcode-solution/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

JS实现

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  if (x < 2) {
    return x;
  }
  let low = 1,
    high = Math.floor(x / 2);
  while (low <= high) {
    const mid = Math.floor(low + (high - low) / 2);
    if (mid * mid === x) {
      return mid;
    }
    if (mid * mid < x) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return high;
};

var mySqrt = (x) => {
  let left = 0,
    right = x,
    result = -1;
  while (left <= right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (mid * mid <= x) {
      result = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return result;
};