Find the square root of a number using a binary search
Given a positive number, return the square root of it. If the number is not a perfect square, return the floor of its square root.
For example,
Input: x = 12
Output: 3
Input: x = 16
Output: 4
Output: 3
Input: x = 16
Output: 4
A naive solution is to consider all positive numbers starting from 1 and find the first number i for which i2 is greater than the given number x. Then i-1 would be the floor of the square root of x.
Following is the C, Java, and Python program that demonstrates it:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <stdio.h> // Function to find the floor of the square root of `x` int findSqrt(int x) { // find the first positive number `i` such that `i×i` is greater than `x` int i = 1; while (i*i <= x) { i++; } return i - 1; } int main(void) { for (int i = 0; i <= 16; i++) { printf("sqrt(%d) = %d\n", i, findSqrt(i)); } return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Main { // Function to find the floor of the square root of `x` public static int sqrt(int x) { // find the first positive number `i` such that `i×i` is greater than `x` int i = 1; while (i*i <= x) { i++; } return i - 1; } public static void main(String[] args) { for (int i = 0; i <= 16; i++) { System.out.printf("sqrt(%d) = %d\n", i, sqrt(i)); } } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Function to find the floor of the square root of `x` def sqrt(x): # find the first positive number `i` such that `i×i` is greater than `x` i = 1 while i*i <= x: i = i + 1 return i - 1 if __name__ == '__main__': for i in range(17): print(f'sqrt({i}) = {sqrt(i)}') |
Output:
sqrt(0) = 0
sqrt(1) = 1
sqrt(2) = 1
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(6) = 2
sqrt(7) = 2
sqrt(8) = 2
sqrt(9) = 3
sqrt(10) = 3
sqrt(11) = 3
sqrt(12) = 3
sqrt(13) = 3
sqrt(14) = 3
sqrt(15) = 3
sqrt(16) = 4
sqrt(0) = 0
sqrt(1) = 1
sqrt(2) = 1
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(6) = 2
sqrt(7) = 2
sqrt(8) = 2
sqrt(9) = 3
sqrt(10) = 3
sqrt(11) = 3
sqrt(12) = 3
sqrt(13) = 3
sqrt(14) = 3
sqrt(15) = 3
sqrt(16) = 4
The time complexity of the above solution is O(√x) and doesn’t require any extra space. We can improve the time complexity to O(log(x)) with the help of the binary search algorithm. The algorithm can be implemented as follows in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include <stdio.h> // Function to find the square root of `x` using the binary search algorithm. // If `x` is not a perfect square, return the floor of the square root int findSqrt(int x) { // base case if (x < 2) { return x; } // to store floor of `sqrt(x)` int result; // the square root of `x` cannot be more than `x/2` for `x > 1` int start = 1; int end = x/2; while (start <= end) { // find the middle element int mid = (start + end) / 2; long sqr = mid*mid; // return `mid` if `x` is a perfect square if (sqr == x) { return mid; } // if `mid×mid` is less than `x` else if (sqr < x) { // discard left search space start = mid + 1; // update result since we need a floor result = mid; } // if `mid×mid` is more than `x` else { // discard the right search space end = mid - 1; } } // return result return result; } int main(void) { for (int i = 0; i <= 16; i++) { printf("sqrt(%d) = %d\n", i, findSqrt(i)); } return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
class Main { // Function to find the square root of `x` using the binary search algorithm. // If `x` is not a perfect square, return the floor of the square root public static int sqrt(int x) { // base case if (x < 2) { return x; } // to store floor of `sqrt(x)` int result = 0; // the square root of `x` cannot be more than `x/2` for `x > 1` int start = 1; int end = x/2; while (start <= end) { // find the middle element int mid = (start + end) / 2; long sqr = mid*mid; // return `mid` if `x` is a perfect square if (sqr == x) { return mid; } // if `mid×mid` is less than `x` else if (sqr < x) { // discard left search space start = mid + 1; // update result since we need a floor result = mid; } // if `mid×mid` is more than `x` else { // discard the right search space end = mid - 1; } } // return result return result; } public static void main(String[] args) { for (int i = 0; i <= 16; i++) { System.out.printf("sqrt(%d) = %d\n", i, sqrt(i)); } } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
# Function to find the square root of `x` using the binary search algorithm. # If `x` is not a perfect square, return the floor of the square root def sqrt(x): if x < 2: # base case return x # to store floor of `sqrt(x)` result = 0 # the square root of `x` cannot be more than x/2 for `x` > 1 start = 1 end = x // 2 while start <= end: # find the middle element mid = (start + end) // 2 sqr = mid*mid # return `mid` if `x` is a perfect square if sqr == x: return mid # if `mid×mid` is less than `x` elif sqr < x: # discard left search space start = mid + 1 # update result since we need a floor result = mid # if `mid×mid` is more than `x` else: # discard the right search space end = mid - 1 # return result return result if __name__ == '__main__': for i in range(16 + 1): print(f'sqrt({i}) = {sqrt(i)}') |
Output:
sqrt(0) = 0
sqrt(1) = 1
sqrt(2) = 1
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(6) = 2
sqrt(7) = 2
sqrt(8) = 2
sqrt(9) = 3
sqrt(10) = 3
sqrt(11) = 3
sqrt(12) = 3
sqrt(13) = 3
sqrt(14) = 3
sqrt(15) = 3
sqrt(16) = 4
sqrt(0) = 0
sqrt(1) = 1
sqrt(2) = 1
sqrt(3) = 1
sqrt(4) = 2
sqrt(5) = 2
sqrt(6) = 2
sqrt(7) = 2
sqrt(8) = 2
sqrt(9) = 3
sqrt(10) = 3
sqrt(11) = 3
sqrt(12) = 3
sqrt(13) = 3
sqrt(14) = 3
sqrt(15) = 3
sqrt(16) = 4
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)