Algotree > Algorithms > Binary Search > Square Root using Binary Search

Square Root using Binary Search

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

The floor and ceiling functions return us the nearest integer up or down on a number line for a given float value.
Example: floor (4.22) = 4 and ceiling (4.22) = 5

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

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"First, solve the problem. Then, write the code. - John Johnson"