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 | Inputnumber | 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 )
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