# Find square root of a number using binary search algorithm

Given a positive number, find square root of it. If the number is not a perfect square, then return floor of its square root.

For example,

Input: x = 12
Output: 3

Input: x = 16
Output: 4

Naive solution is to consider all positive numbers starting from 1, and find the first number i for which i*i is greater than the given number x. Then, i-1 would be the floor of square root of x.

The time complexity of above solution is O(√x). We can improve the time complexity to O(log(x)) with the help of binary search algorithm. The algorithm can be implemented as follows in C:     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest
TechCrush

Recursive solution to this problem:

int sqrt(int num, int so_far, int s, int e){
if( s <= e){
int mid = (s+e)/2;
if( mid * mid == num) return mid;
else if(mid*mid < num){
so_far = mid;
return sqrt(num,so_far,mid+1, e);
}else return sqrt(num, so_far,s, mid-1);
}
return so_far;
}