Integer square root, python (11.4)

#1
  1. Why does the code not work if we include a third condition in the while loop i.e. return mid if mid_squared = k? For example:

def square_root(k):
left = 0
right = k
while left < right:
mid = (left + right)//2
mid_squared = mid*mid
if mid_squared < k:
left = mid + 1
elif mid_squared > k:
right = mid - 1
else: ##mid_squared = k
return mid
return left - 1

for example, if k= 4, we begin with [0,4]. mid = 2, so we could simply return mid directly.

  1. Also, in each iteration, we are either move left to mid + 1 or right to mid - 1. I noticed that the code fails if we move left and right to mid, instead of mid + 1 and mid - 1, respectively. Could you throw some light on why this approach will not work?

Thanks!

0 Likes

#2

Hi @Denace,

I will say you shall try to print the values of left, right, and mid to help you debug on this. It is the basic learning process of debugging but I think you definitely can figure out by yourself.

0 Likes

#3

I figured it out, no problem.

0 Likes