2分探索
2分探索 Binary Search
Pythonで2分探索を実装します。
二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。 出典: フリー百科事典『ウィキペディア（Wikip...
yottagin.com
2019-05-06 23:07
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