【JavaScript】Math.sqrt()を使わずに非負整数の平方根を求める方法

今回は、非負整数を受け取り、その平方根を計算して返すJavaScript関数を作成する方法を解説します。ただし、Math.sqrt()は使用しません。また、結果が浮動小数点数になる場合は、小数点以下を切り捨てて整数として返すものとします。

問題の概要

例えば、入力が「15」の場合、正確な平方根（約3.872）を返す必要はありません。それより小さい最も近い整数である「3」を返せばよいことになります。

このような問題に対しては、二分探索（バイナリサーチ）アルゴリズムを活用することで、効率的に平方根へと収束させることができます。

実装コード

実際のコードは以下の通りです。

const squareRoot = (num = 1) => {
    let l = 0;
    let r = num;
    while(l <= r) {
        const mid = Math.floor((l + r) / 2);
        if(mid ** 2 === num){
            return mid;
        } else if(mid ** 2 > num){
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return r;
};

console.log(squareRoot(4));
console.log(squareRoot(729));
console.log(squareRoot(15));
console.log(squareRoot(54435));

コードの解説

この関数の仕組みを簡単に説明します。

• 探索範囲の下限 l を0、上限 r を対象の数値そのものに設定します。
• 範囲の中央値 mid を求め、その2乗が対象の数値と一致すれば、それが平方根です。
• mid の2乗が対象より大きければ探索範囲の上限を狭め、小さければ下限を広げます。
• ループが終了した時点での r が、小数点以下を切り捨てた平方根となります。

二分探索により、毎回探索範囲が半分になるため、非常に大きな数でも高速に計算できます。計算量は O(log n) です。

実行結果

コンソールには次のように出力されます。

2
27
3
233

それぞれ、「4の平方根は2」「729の平方根は27」「15の平方根は約3.87なので3」「54435の平方根は約233.31なので233」と正しく計算できていることが確認できます。

まとめ

Math.sqrt()のような組み込みメソッドに頼らなくても、二分探索を使えば平方根を効率よく求められます。アルゴリズムの学習やコーディング面接の対策としても役立つテクニックなので、ぜひ理解しておきましょう。