69. Sqrt(x)

Leetcode 问题: 69. Sqrt(x)
Categories:
Tags:

题目

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

给予一个 非负整数 x，找寻这个整数的平方根，如果平方根有小数点的话，只需要回传整数的部分即可

Example

Input: x = 4
Output: 2

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

演算法

1. 二分法切割要检查的整数范围

整数最大的平方根顶多是自己，所以可以知道检查的数字上限就是自己

  • 左侧检查整数: 0
  • 右侧检查整数: 自己

取左右整数，左右逼近到可能出现的平方根数字，如果「左侧检查整数」与「右侧检查整数」没有相交，表示还可以再寻找

将整数切割成一半，拿左右整数的平均数当作切割点，可以把数字切割成一半，减少要检查的范围

2. 检查切割点的平方数

A. 如果「中间数的平方」小于等于「要检查的数字」

平方数尚未超过「要检查的数字」，所以目前的「中间数」是潜在 可能的平方根

如果有更符合的数字，一定在「中间数」右方区块，所以将「左侧检查整数」设定为「目前中间数 + 1」，检查右边区块

B. 如果「中间数的平方」大于「要检查的数字」

中间数平方后已经超过原本要检查的数字了，所以一定是比中间数小的数字才能够符合

所以符合的数字一定在「中间数」左方，所以将「右侧检查整数」设定为「目前中间数 - 1」，检查左边区块

答案

JavaScript

/**
 * @param {number} checkNumber
 * @return {number}
 */
var mySqrt = function(checkNumber) {
    if (checkNumber <= 1) {
        // 如果要检查的数字小于 1，最接近的平方整数就是自己
        return checkNumber;
    }
    // 左侧检查整数
    let leftNumber = 0;
    // 右侧检查整数，设定为传入的数字
    let rightNumber = checkNumber;
    // 平方根数字
    let checkNumberSqrt = 0;

    while (leftNumber <= rightNumber) {
        // 如果「左侧检查整数」与「右侧检查整数」没有相交，表示还可以再寻找
        // 寻找两侧数字的「中间平均数」
        let middleNumber = Math.floor((rightNumber + leftNumber) / 2);

        if (middleNumber * middleNumber <= checkNumber) {
            // 如果「中间数的平方」小于等于「要检查的数字」
            // 平方数尚未超过「要检查的数字」，所以目前的「中间数」是潜在可能的平方根
            checkNumberSqrt = middleNumber;
            // 符合的数字一定在「中间数」右方，所以将「左侧检查整数」设定为「目前中间数 + 1」，检查右边区块
            leftNumber = middleNumber + 1;
        } else {
            // 如果「中间数的平方」大于「要检查的数字」
            // 符合的数字一定在「中间数」左方，所以将「右侧检查整数」设定为「目前中间数 - 1」，检查左边区块
            rightNumber = middleNumber - 1
        }
    }

    return checkNumberSqrt;
};

参考资料