Pythonで平方根の整数部分を求める方法｜組み込み関数を使わない二分探索アルゴリズム

はじめに

本記事では、非負整数 n が与えられたとき、r * r = n を満たす数 r を求め、その結果を最も近い整数へ切り捨てる方法を解説します。重要なポイントは、組み込みの平方根関数（math.sqrt など）を使用せずに実装するという点です。

例えば、入力が 1025 の場合、出力は 32 となります。これは 32 × 32 = 1024 ≤ 1025 であり、33 × 33 = 1089 > 1025 だからです。

解法のアプローチ：二分探索

この問題は「二分探索（バイナリサーチ）」を使うことで効率的に解けます。探索範囲を半分ずつ絞り込んでいくことで、計算量は O(log n) に抑えられます。

アルゴリズムの手順

1. n <= 1 の場合は、そのまま n を返します（0 と 1 の平方根はそれぞれ 0 と 1 になるため）。
2. 探索範囲の下限 start := 1、上限 end := n を設定します。
3. start < end の間、以下を繰り返します。
   • 中央値 mid := start + end / 2 を計算します。
   • mid * mid <= n であれば、start := mid + 1 とし、より大きい候補を探します。
   • そうでなければ、end := mid とし、探索範囲を狭めます。
4. 最後に start - 1 を返します。これが切り捨てられた平方根です。

実装例

以下に Python での具体的な実装を示します。

class Solution:
    def solve(self, n):
        if n <= 1:
            return n
        start, end = 1, n
        while start < end:
            mid = start + end >> 1
            if mid * mid <= n:
                start = mid + 1
            else:
                end = mid
        return start - 1

ob = Solution()
print(ob.solve(1025))

入力

1025

出力

32

コードのポイント

• start + end >> 1 はビットシフト演算を使った整数除算で、(start + end) // 2 と同じ意味です。高速に中央値を求められます。
• ループ終了時の start は「条件を満たさない最初の値」を指しているため、-1 することで答えが得られます。
• 大きな数に対しても O(log n) の時間で処理できるため、ニュートン法などと並んで効率的な手法の一つです。

まとめ

組み込みの平方根関数を使わずに整数の平方根を求めるには、二分探索が有効です。探索範囲を繰り返し半分に絞り込むことで、正確かつ高速に切り捨てた平方根を計算できます。競技プログラミングや面接対策としても頻出のテクニックなので、ぜひマスターしておきましょう。