Square Root using Binary Search


Finding square root algorithm makes use of binary search to find the (floor of) square root of a given number N.

Case 1 :  If mid is the middle number in the range 1 … N and N == ( mid * mid ), the middle number is evidently the square root of the number N.

Case 2 :  If ( mid * mid ) is greater than N, it means that mid is greater than the floor of the square root of N so we binary search in the range 1 … mid-1.

Case 3 :  If ( mid * mid ) is less than N, it may or may not be the floor of the square root of N so we store mid as the temporary square root and proceed to search for square root in the range 1 … mid+1.


Example

Consider finding the square root of N = 15.

Step Input
number
Beginning End Mid Reasoning
1 15 1 15 8 Since 8 * 8 > 15, continue binary search in lower range ( 1 … 7 ).
2 15 1 7 4 Since 4 * 4 > 15, continue binary search in lower range ( 1 … 3 ).
3 15 1 3 2 Since 2 * 2 < 15, 2 could well be the floor of the square root of 15.
Store 2 as the temporary square root and check if there is a number bigger than 2 that could also be the floor of square root of 15.
Continue binary search in higher range ( 3, 3 ).
4 15 3 3 3 Since 3 * 3 < 15, update the floor of the square root of 15 to 3.
Since Beginning equals End, the algorithm terminates here.

Time complexity : Log ( N )

Why is mid calculated as mid = beg + (end-beg)/2 ?


Program for finding the floor ( square_root ( n ) ) of a number using binary search.

#!/usr/bin/python3 

def SquareRootFloor (beg, end, n) :
    
    ans_sqrt = n;

    while (beg <= end) :

        mid = int(beg + (end-beg)/2);
        print ("beg : " + str(beg) + " end : " + str(end) + " mid : " + str(mid))

        if ( mid*mid == n ) : 
            return mid 
        elif ( mid * mid > n) :
            end = mid - 1 
        else :
            # If mid*mid < n, it does not certainly mean that mid is the floor(square_root(n)), it may / may not be.
            # Example n = 15, when mid becomes 2. mid*mid < 15 so 2 could well be the floor(square_root(15)) so store it
            # as the answer and continue the search for a bigger number that could also be the floor(square_root(15))*/
            print ("Store square root as mid (" + str(mid) + ")")
            ans_sqrt = mid 
            beg = mid + 1 
    
    return ans_sqrt;

num = 100 
print ("Finding square root of : " + str(num))
sqrt_n = SquareRootFloor (1, num, num)
print("Output : "+ str(sqrt_n)+"\n")

num = 15
print ("Finding square root of : " + str(num))
sqrt_n = SquareRootFloor (1, num, num)
print("Output : "+ str(sqrt_n))

Output

Finding square root of : 100
beg : 1 end : 100 mid : 50
beg : 1 end : 49 mid : 25
beg : 1 end : 24 mid : 12
beg : 1 end : 11 mid : 6
Store square root as mid (6)
beg : 7 end : 11 mid : 9
Store square root as mid (9)
beg : 10 end : 11 mid : 10
Output : 10

Finding square root of : 15
beg : 1 end : 15 mid : 8
beg : 1 end : 7 mid : 4
beg : 1 end : 3 mid : 2
Store square root as mid (2)
beg : 3 end : 3 mid : 3
Store square root as mid (3)
Output : 3

#include<iostream>
using namespace std;

typedef unsigned long long ULL;
int SquareRootFloor (ULL beg, ULL end, ULL n) { 
            
    int ans_sqrt = n;

    while (beg <= end) {

        ULL mid = beg + (end-beg)/2;
        cout << "beg : " << beg << " end : " << end << " mid : " << mid << endl;

        if (mid*mid == n) {
            return mid;
        } else if (mid*mid > n) {
            end = mid - 1;
        } else {
            /* If mid*mid < n, it does not certainly mean that mid is the floor(square_root(n)), it may / may not be.
               Example n = 15, when mid becomes 2. mid*mid < 15 so 2 could well be the floor(square_root(15)) so store it
               as the answer and continue the search for a bigger number that could also be the floor(square_root(15))*/
            cout << "Store square root as mid (" << mid << ")" << endl;
            ans_sqrt = mid; 
            beg = mid + 1;
        }
    }
    return ans_sqrt;
}

int main() {

    ULL n, sqrt_n;
    cin >> n;
    cout << "Input : " << n << endl;
    sqrt_n = SquareRootFloor (1, n, n);
    cout << "Output : " << sqrt_n << endl;
    return 0;
}

Sample run 1

Input : 100
beg : 1 end : 100 mid : 50
beg : 1 end : 49 mid : 25
beg : 1 end : 24 mid : 12
beg : 1 end : 11 mid : 6
Store square root as mid : 6
beg : 7 end : 11 mid : 9
Store square root as mid : 9
beg : 10 end : 11 mid : 10
Output : 10

Sample run 2

Input  : 15
beg : 1 end : 15 mid : 8
beg : 1 end : 7 mid : 4
beg : 1 end : 3 mid : 2
Store square root as mid:2
beg : 3 end : 3 mid : 3
Store square root as mid : 3
Output : 3
public class SquareRoot {

    int SquareRootFloor (int beg, int end, int n) { 
    
        int ans_sqrt = n;
    
        while (beg <= end) {
    
            int mid = beg + (end-beg)/2;
            System.out.println("beg : " + beg + " end : " + end + " mid : " + mid);
    
            if (mid*mid == n) {
                return mid;
            } else if (mid*mid > n) {
                end = mid - 1;
            } else {
                /* If mid*mid < n, it does not certainly mean that mid is the floor(square_root(n)), it may / may not be. 
                   Example n = 15, when mid becomes 2. mid*mid < 15 so 2 could well be the floor(square_root(15)) so store it
                   as the answer and continue the search for a bigger number that could also be the floor(square_root(15))*/
                System.out.println("Store square root as mid (" + mid + ")");
                ans_sqrt = mid; 
                beg = mid + 1;
            }
        }
        return ans_sqrt;
    }   

    public static void main (String[] args) {

        int n, sqrt_n;
        n = 100;
        SquareRoot sr = new SquareRoot();

        System.out.println("Find square root of : " + n); 
        sqrt_n = sr.SquareRootFloor (1, n, n); 
        System.out.println("Output : " + sqrt_n + "\n"); 

        n = 15; 
        System.out.println("Find square root of : " + n); 
        sqrt_n = sr.SquareRootFloor (1, n, n); 
        System.out.println("Output : " + sqrt_n); 

        sr = null;
    }   
}

Output

Find square root of : 100
beg : 1 end : 100 mid : 50
beg : 1 end : 49 mid : 25
beg : 1 end : 24 mid : 12
beg : 1 end : 11 mid : 6
Store square root as mid (6)
beg : 7 end : 11 mid : 9
Store square root as mid (9)
beg : 10 end : 11 mid : 10
Output : 10

Find square root of : 15
beg : 1 end : 15 mid : 8
beg : 1 end : 7 mid : 4
beg : 1 end : 3 mid : 2
Store square root as mid (2)
beg : 3 end : 3 mid : 3
Store square root as mid (3)
Output : 3



Copyright (c) 2019-2021, Algotree.org.
All rights reserved.