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

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
``````