def binsearch_sqrt(num):
low = 1
high = num
guess = low + (high - low) / 2
count = 0
while guess != low and guess != high:
sqr = guess * guess
if sqr == num:
break
elif(sqr < num):
low = guess
else:
high = guess
guess = low + (high - low) / 2
count += 1
else:
if abs(low * low - num) < abs(high * high - num):
guess = low
else:
guess = high
return count, guess
def print_result(num, count, guess):
print(count, 'iterations')
print(num, '~=', guess * guess)
print(num**0.5, '~=', guess)
print()
print_result(2, *binsearch_sqrt(2))
print_result(9, *binsearch_sqrt(9))
ZGVmIGJpbnNlYXJjaF9zcXJ0KG51bSk6CiAgICBsb3cgPSAxCiAgICBoaWdoID0gbnVtCiAgICBndWVzcyA9IGxvdyArIChoaWdoIC0gbG93KSAvIDIKICAgIGNvdW50ID0gMAogICAgd2hpbGUgZ3Vlc3MgIT0gbG93IGFuZCBndWVzcyAhPSBoaWdoOgogICAgICAgIHNxciA9IGd1ZXNzICogZ3Vlc3MKCiAgICAgICAgaWYgc3FyID09IG51bToKICAgICAgICAgICAgYnJlYWsKICAgICAgICBlbGlmKHNxciA8IG51bSk6CiAgICAgICAgICAgIGxvdyA9IGd1ZXNzCiAgICAgICAgZWxzZToKICAgICAgICAgICAgaGlnaCA9IGd1ZXNzCgogICAgICAgIGd1ZXNzID0gbG93ICsgKGhpZ2ggLSBsb3cpIC8gMgogICAgICAgIGNvdW50ICs9IDEKCiAgICBlbHNlOgogICAgICAgIGlmIGFicyhsb3cgKiBsb3cgLSBudW0pIDwgYWJzKGhpZ2ggKiBoaWdoIC0gbnVtKToKICAgICAgICAgICAgZ3Vlc3MgPSBsb3cKICAgICAgICBlbHNlOgogICAgICAgICAgICBndWVzcyA9IGhpZ2gKICAgIHJldHVybiBjb3VudCwgZ3Vlc3MKCmRlZiBwcmludF9yZXN1bHQobnVtLCBjb3VudCwgZ3Vlc3MpOgogICAgcHJpbnQoY291bnQsICdpdGVyYXRpb25zJykKICAgIHByaW50KG51bSwgJ349JywgZ3Vlc3MgKiBndWVzcykKICAgIHByaW50KG51bSoqMC41LCAnfj0nLCBndWVzcykKICAgIHByaW50KCkKCnByaW50X3Jlc3VsdCgyLCAqYmluc2VhcmNoX3NxcnQoMikpCnByaW50X3Jlc3VsdCg5LCAqYmluc2VhcmNoX3NxcnQoOSkp