69. Sqrt(x)


给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
 
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
 
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
 
 
 
示例 1:
 
输入:x = 4
输出:2
示例 2:
 
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
 
 public int mySqrt(int x) {
        int left = 0, right = x;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (mid * mid <= x) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

二分查找

二分的本质并非“单调性”,而是“边界”,只要找到某种性质,使得整个区间一分为二,那么就可以用二分把边界点二分出来。

算法模板

    int search01(int[] nums, int left, int right, int target) {
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    int search02(int[] nums, int left, int right, int target) {
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
  • 作者:低调做个路人 (扫码联系作者)
  • 发表时间:2021-12-03 16:37:20
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 评论

    a's'd
    111
    gf
    gkggjgjkgkjgjk
    张三
    111
    1
    123