The idea is simple. We will use binary search to find the square root of the number. If the given number is not a perfect square then we will simply take the floor value of the root of the number.. Algorithm to find the square root of a number in log time is given below along with its implementation in C++.

1. set start=1

2. set end=n

3. do while (start<=end):

4. set mid=(start+end)/2

5. if (mid*mid=n) return mid

6. else if (mid*mid<n)

7. set ans=mid

8. set start=mid+1

9. else

10. set end=mid-1

11. return ans

**For example:**if n = 10 then answer is 3 and if n==25 then answer is 5**Algorithm:**1. set start=1

2. set end=n

3. do while (start<=end):

4. set mid=(start+end)/2

5. if (mid*mid=n) return mid

6. else if (mid*mid<n)

7. set ans=mid

8. set start=mid+1

9. else

10. set end=mid-1

11. return ans

**PROGRAM:**

#include <bits/stdc++.h> using namespace std; int findFloorRoot(int n){ int start=1,end=n; int ans; while(start<=end){ //calculate middle value int mid=(start+end)/2; //if nis a perfect square of mid then return mid if(mid*mid==n) return mid; else if(mid*mid<n){ ans=mid; //if n is not a perfect square then take the floor value start=mid+1; } else end=mid-1; } return ans; } int main(){ int n; cout<<"\nEnter the number: "; cin>>n; int ans=findFloorRoot(n); cout<<"\nThe root of the n is: \n\n"; cout<<ans; cout<<"\n"; return 0; }

**OUTPUT:**

EmoticonEmoticon