69. Sqrt(x)

非負整数 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 を超えない最大の値になる。

---