Pythonで平方根を求める：ライブラリ不要の二分探索によるsqrt(x)の実装方法

非負の整数 x が与えられたとき、標準ライブラリの関数を使わずに x の平方根を求めることを考えます。つまり、sqrt(x) を計算する独自の関数を実装する必要があります。この関数では、結果の小数点以下は切り捨て、整数部分のみを返します。

例を挙げると、x = 4 の場合は答えは 2 です。x = 8 の場合も答えは 2 になります。なぜなら sqrt(8) ≈ 2.82842 ですが、整数部分だけを取り出すためです。

アルゴリズムの考え方：二分探索

この問題は二分探索（バイナリサーチ）を使うと効率的に解けます。平方根の候補となる範囲を半分ずつ絞り込んでいくことで、高速に答えを求められます。

手順は以下の通りです。

• 探索範囲の下限 l = 1、上限 h = x + 1、答えを格納する answer = 0 で初期化する
• h > l の間、以下を繰り返す
  • mid = (h + l) / 2 を計算する
  • mid × mid ≤ x であれば、l := mid + 1 とし、answer = mid を更新する
  • そうでなければ、h = mid とする
• ループ終了後、answer を返す

この方法の計算量は O(log x) であり、x が非常に大きい場合でも高速に動作するのが特徴です。

Pythonでの実装例

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        low = 1
        high = x + 1
        ans = 0
        while high > low:
            mid = (high + low) // 2
            print(low, mid, high)
            if mid * mid <= x:
                low = mid + 1
                ans = mid
            else:
                high = mid
        return ans

ob1 = Solution()
print(ob1.mySqrt(4))
print(ob1.mySqrt(16))
print(ob1.mySqrt(7))
print(ob1.mySqrt(15))

入力

print(ob1.mySqrt(4))
print(ob1.mySqrt(16))
print(ob1.mySqrt(7))
print(ob1.mySqrt(15))

出力

2
4
2
3

コードのポイント

• 整数除算を使用： Pythonでは // 演算子を使うことで、mid を常に整数として扱えます。
• 境界条件への注意： 上限を x + 1 に設定することで、x = 0 や x = 1 のような小さな入力にも正しく対応できます。
• answer の更新タイミング： mid² が x 以下のときだけ answer を更新することで、「x を超えない最大の整数」が正しく記録されます。

このように、二分探索の基本的な枠組みを少し工夫するだけで、数学ライブラリに頼らずに平方根の整数部分を正確に求めることができます。競技プログラミングや技術面接でも頻出のテーマなので、ぜひマスターしておきましょう。