How to find the nearest square root to nearest using binary search using python

Question

How to find the nearest square root of number?

• If square root present then I need the exact square toot, otherwise the previous of square root.

Example is below:

• squre_root(101) = 10
• squre_root(100) = 10

Approach

• Find the mid number of square root to find
• for 101: find the mid, that is 51
• since 51 * 51 <= 101 then 51 will be divided by half
• Like at last by binary search I will get 10

Sample Code :

def find_sqrt(k):
    begin, last = 1, k
    mid = int((begin + last)/ 2)
    
    while begin < mid:
        if mid * mid => k:
            mid = int(mid/ 2)
        if mid * mid <= k:
            mid += 1
    return mid

I had found guess nearest square root in python while researching.

Answer 1

I have translated the psuedo-code from here

def find_sqrt(k):
    begin, last = 1, k

    while begin < last:
        mid = int((begin + last) / 2)
        if mid * mid <= k:
            begin = mid + 1
        else:
            last = mid
    return begin - 1


print(find_sqrt(100))
print(find_sqrt(101))