侧边栏壁纸
博主头像
小顺

一帆风顺 ⛵️⛵️⛵️

  • 累计撰写 70 篇文章
  • 累计创建 0 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

x的平方根--二分查找

小顺
2022-12-12 / 0 评论 / 0 点赞 / 38 阅读 / 274 字
package com.apesblog.day_20221212;

/**
 * @author ZhangYuShun
 * @since 2022/12/12
 * x的平方根
 * 在不使用 sqrt(x) 函数的情况下,得到 x的平方根的整数部分
 * <p>
 * 解法一:二分查找
 * x的平方根肯定在0到x之间,使用二分查找定位该数字,该数字的平方一定是最接近x的,m平方值如果
 * 大于x、则往左边找,如果小于等于x则往右边找
 * 找到0和X的最中间的数m,
 * 如果m * m > x,则m取x/2到x的中间数字,直到m * m < x,m则为平方根的整数部分
 * 如果m * m <= x,则取0到x/2的中间值,知道两边的界限重合,找到最大的整数,则为x平方根的整数
 * 部分
 * 时间复杂度:O(logN)
 */
public class SquareRoot {

    public static void main(String[] args) {
        System.out.println(binarySearch(24));

    }

    public static int binarySearch(int x) {
        int l = -1;
        int r = x;
        while (l + 1 != r) {
            int mid = (l + r) / 2;
            if (mid * mid <= x) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l;
    }
}

image-20221212182018281

0

评论区