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;
};

參考資料