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