I got this question in my Assembly lab. I had to code this up for 8086 processor. But I’ll be writing about the approach here.
If `r` is the square root of `X`, then r*r == X.
We can use the binary search aproach to search for this number `r`, since it would lie between [1,X].
Thus, if r*r< X, then we can search for the number in upper right of the function?
If r*r > X, then we should expect the square root to be on the left side of the function?
lower_bound = 0
upper_bound = len(A)while lower_bound < upper_bound:
mid = (lower_bound+upper_bound)/2
if mid*mid == A:
if mid*mid < A:
lower_bound = mid+1
ans = lower_bound if mid*mid > A:
upper_bound = mid-1