Writing Your Own Sqrt Function

Photo by Volkan Olmez on Unsplash

Function Input and Output :

Basically, the requirement is to give the square root of the input number in integer form, if it is in float (decimal) then we will floor the value and make it an integer.

Algorithm of Function :

The approach I used is simple and easy to understand but only works for the function with such requirements as mentioned above.

The approach is the same as in Binary Search Approach. We just do a binary search for the number in the numbers less the input numbers. We know the square root of the number cannot be greater than half of the number. (e.g if N is the input number, the square root can’t be greater than N/2)

So we will binary search for the number, the square of which is equal to the input number (N). if we don’t find any such number we will return the number the square of which is close to the input number.

Code of the Function :

If you don’t know the algorithm of binary search then read the below article first

Article on Binary Search Algorithm

The only change is that in a simple binary search if the number is not found we return the -1, while in this case we just return the number which is close to our desired number. (Our desired number is the number, the square of which is equal to the input number)

Here is the code of the function below in C++ Language

Space and Time Complexity :

Time Complexity = O(long)

Space Complexity = O(1)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Abdullah Afzal

A student, always trying to look up for cool things and do something creative.