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


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given function tex_adb65897f29a966c6e4abe82e899e098 Teaching Kids Programming - Binary Search Algorithm to Compute the Square Root algorithms binary search math python teaching kids programming youtube video where x is non-negative, we can plot the graph as below:

graph-y-sqr-x Teaching Kids Programming - Binary Search Algorithm to Compute the Square Root algorithms binary search math python teaching kids programming youtube video

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
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
1
2
for i in range(10):
    print("Sqrt " + str(i) + " = " + str(Sqrt(i)))
for i in range(10):
    print("Sqrt " + str(i) + " = " + str(Sqrt(i)))
1
2
3
4
5
6
7
8
9
10
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
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:

1
2
3
4
5
6
Sqrt(0.1234)**2
# 0.12340314779430628
Sqrt(0.9)**2
# 0.9000026455614716
# Sqrt(0.5)**2
0.500001078704372
Sqrt(0.1234)**2
# 0.12340314779430628
Sqrt(0.9)**2
# 0.9000026455614716
# Sqrt(0.5)**2
0.500001078704372

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
391 words
Last Post: List Calculator Algorithm
Next Post: Algorithms to Sum using Distinct Positive Factorial Numbers

The Permanent URL is: Teaching Kids Programming – Binary Search Algorithm to Compute the Square Root

Leave a Reply