2分探索
2分探索の練習をします。
2分探索を使って、ある自然数の平方根以下で最大となる整数を求めてます。
例えば、500であれば\( \sqrt 500 = 22.360679774…\)で、求めたい数字は22になります。
def integer_squareroot(x): imin = 0 imax = x while imin <= imax: imid = (imin + imax) // 2 imid_squared = imid ** 2 if imid_squared <= x: imin = imid + 1 else: imax = imid - 1 return imin - 1