Square Root using Binary Search

Binary Search looks for a value in a sorted array. It compares the middle number of the array with the searched value. If the middle number equals the searched value, the position of the middle number is returned. If the middle number is bigger, the left portion of the array is searched using the same logic (binary search), else the right portion of the array is searched 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 : Binary search implementation to find the floor(square_root(n)) of a number in Java 8


Python

Python : Binary search implementation to find the floor(square_root(n)) of a number in Python 3


C++ : Binary search implementation to find the floor(squareroot(n)) of a number in C++11

#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.