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 of finding the floor of the square root of a number using binary search.

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 of the binary search algorithm for finding the square root of a number N : Log ( N )

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

Java

Java program to find the floor(square_root(n)) of a number using binary search.


Python

Python program to find the floor(square_root(n)) of a number using binary search.


C++ program to find the floor(square_root(n)) of a number using binary search.

#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

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