x的平方根

[PisecesPeng]

x的平方根

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

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

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

题目地址: https://leetcode-cn.com/problems/sqrtx/

[PisecesPeng]

解题思路

• 通过二分法, 找出最接近x值的那个数;

代码

private static int func(int x) {
    if (x < 2) return x;

    long left = 0, right = x, m = (left + right) / 2;
    while (true) {
        long rTmp = m * m;
        if (rTmp == x) {
            return Long.valueOf(m).intValue();
        } else if (rTmp > x) {
            right = m;
            m = (left + right) / 2;
        } else {
            long pTmp = (m + 1) * (m + 1);
            if (pTmp == x) return Long.valueOf(m + 1).intValue();
            else if (pTmp > x) return Long.valueOf(m).intValue();
            else {
                left = m;
                m = (left + right) / 2;
            }
        }
        if (left >= right - 1) return 0;
    }
}

[PisecesPeng]

LeetCode题解

解题思路

• 通过二分法, 找出最接近x值的那个数;

代码

private static int func(int x) {
    int l = 0, r = x, ans = -1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if ((long) mid * mid <= x) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return ans;
}