Teaching Kids Programming – Binary Search Algorithm to Compute the Square Root

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given function where x is non-negative, we can plot the graph as below:

Compute the Square Root by using Binary Search Algorithm

Since the function is monotone increasing, we can use the binary search algorithm to find the value which is closest or equal to the square root.

The left boundary is zero. If the x is between 0 and 1, we can set the upperbound to 1 and if the x is greater than 1, we can set the upperbound to x and lowerbound to 1.

Within this range [0, upper], we can do the binary search and continue until the result difference is no more than e.

def Sqrt(x, e = 1e-5):
    if x < 0:
        return None
    if x < 1:
        left, right = 0, 1
    else:
        left, right = 1, x
    mid, cur = 0, 0
    while abs(cur - x) > e:
        mid = (left + right) / 2
        cur = mid * mid
        if cur > x:
            right = mid
        else:
            left = mid
    return mid

for i in range(10):
    print("Sqrt " + str(i) + " = " + str(Sqrt(i)))

Sqrt 0 = 0
Sqrt 1 = 1
Sqrt 2 = 1.414215087890625
Sqrt 3 = 1.7320518493652344
Sqrt 4 = 2.0
Sqrt 5 = 2.2360658645629883
Sqrt 6 = 2.449490547180176
Sqrt 7 = 2.645751476287842
Sqrt 8 = 2.8284263610839844
Sqrt 9 = 3.0000014305114746

And the square root below 1:

Sqrt(0.1234)**2
# 0.12340314779430628
Sqrt(0.9)**2
# 0.9000026455614716
# Sqrt(0.5)**2
0.500001078704372

–EOF (The Ultimate Computing & Technology Blog) —