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.

 

Download   Run Code

 
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:

 

Download   Run Code

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

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 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
TechCrush
Guest

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;
}