题目

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

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

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

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

题解

1.二分法
a.本人写的
由于是要向下取整,也就是说取left 所以考虑从左向右收敛,来获取左边界,一般 l = mid +1 是从右向左收敛,所以得到的是右边界,也就是向上取整的值

  1. /**
  2.  * @param {number} x
  3.  * @return {number}
  4.  */
  5. var mySqrt = function (x) {
  6.     //二分法
  7.     let l = 0, r = Math.floor(x / 2)
  8.     if (x === 1) return 1
  9.     while (l < r) {
  10.         const mid = l + ((r - l + 1) >> 1)
  11.         if (Math.floor(x / mid) < mid) {
  12.             r = mid - 1
  13.         } else {
  14.             l = mid
  15.         }
  16.     }
  17.     return l
  18. };

b.评论区题解(效率比我高,可能是不用取整)

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
    //二分法
    let l = 0, r = x
    if (x === 1) return 1
    while (l < r - 1) {
        const mid = l + ((r - l) >> 1)
        if (mid * mid <= x) {
            l = mid
        } else {
            r = mid
        }
    }
    return l
};