In this algorithm, we use binary search to find the square root of the number.
It is recommended to go through Binary Search topic first.
At every step, we find out the mid value from start(initialized as 0) and end(initialized as number) and then check if it is the square root (in case of perfect square numbers) or whether we are reaching the square root within give precision by comparing current mid value to previous mid value (in case the number is not a perfect square).
Use binary search to find the square root.
1. Initialize, start = 0, end = number, mid = (start+end)/2.
2. Set prevMid = 0, as the previous mid value.
3. Find diff = absolute difference between prevMid and mid.
4. While mid is not the square root of number (i.e. mid*mid != number) and difference diff is greater than 0.0005,
repeat the following steps:
a. If mid*mid > number, then the square root will be less than mid. So, set end = mid.
b. Else, the square root will be greater than mid. So, set start = mid.
c. Set prevMid = mid
d. Re-evaluate mid = (start+end)/2.
e. Re-evaluate diff from prevMid and mid.
The algorithm strategy is explained with the help of following animation:
If the given number is negative, then square root of the number will be square root of positive part of the number * i (iota).
√-100 = √100 * √-1 = 10i