💡

69. Sqrt(x)

に公開
PHP
LeetCode
tech

非負整数 x が与えられた場合、x の平方根を 小数点以下を切り捨てた最も近い整数 として返してください。返される整数も 非負 でなければなりません。

組み込みの累乗関数や演算子を使用してはいけません。

例えば、C++ では pow(x, 0.5) を、Python では x ** 0.5 を 使用しないでください。

例 1:

入力:
x = 4
出力:
2
説明:
4 の平方根は 2 なので、2 を返します。

例 2:

入力:
x = 8
出力:
2
説明:
8 の平方根は 2.82842... ですが、小数点以下を切り捨てる ため 2 を返します。

二分探索を使った平方根の求め方

  1. 範囲を決める

    • left = 0、right = x で初期化。
    • ただし x が 1 以下ならそのまま返す。

  2. 二分探索の実行

    • mid = (left + right) // 2 を計算。
    • mid^2 が x なら、そのまま mid を返す。
    • mid^2 > x の場合、right = mid - 1 で小さい値を探索。
    • mid^2 < x の場合、left = mid + 1 で大きい値を探索。

  3. 最終的に right を返す

    • right は mid^2 が x を超えない最大の値になる。

Discussion