Program to find the square root of a number

Program to find the square root of a number

One way to find the square root of any number is start from i=0 and keep increasing it until you find that  i² >= n.But this method has complexity = O(√n).

Here's a better way, since the square root of any number lies somewhere between 0 and n. So using binary search (since the numbers 0-n are already sorted ) to find it reduces the complexity of the program to O(Log n).

NOTE: The program shown below prints the floor value of square root in case the number is not a perfect square.

Here's the code:

#include<stdio.h>
 
// Returns floor of square root of x         
int Sqrt(int n) 
{    
    // Base cases
    if (n == 0 || n == 1) 
       return n;
 
    // To implement Binary Search to find the square root
    int start = 1, end = n, ans;   
    while (start <= end) 
    {        
        int mid = (start + end) / 2;
 
        if (mid*mid == n) //if x is a perfect square
            return mid;
 
        if (mid*mid < n){
            start = mid + 1;
            ans = mid;
        } 
        else 
            end = mid - 1;        
    }
    return ans;
}

int main() 
{     
    int n;
    printf("Enter the number: ");
    scanf("%d",&n);
    printf("%d",Sqrt(n));
    return 0;   
}