Algorithm : Implement a fast integer square root function that takes in a 32-bit unsigned integer and returns another 32-bit unsigned integer that is the floor of the square root of the input.
public class SquareRootBinarySearch {
public static void main(String [] args)
{
int [] inputs = {18, 67, 54, 98, 13908};
for(int input : inputs)
{
getSquareRoot(input);
//System.out.println(“The Square Root of “+input + ” is :”+getSquareRoot(input));
}
}
private static int getSquareRoot(int input) {
int high = input;
int low = 1;
int delta = Integer.MAX_VALUE;
int start = 0, end = 0;
boolean canContinue = true;
int result = 0;
while ((low < high) && canContinue)
{
start = low;
end = high;
if (high – low <= 1)
canContinue = false;
int mid = low + (high-low)/2;
//System.out.println(“Low is :”+low + ” and high is:”+high);
int tempSquareRoot = mid * mid;
int tempDelta = Math.abs(tempSquareRoot – input);
if (delta > tempDelta)
{
delta = tempDelta;
result = mid;
}
if (tempSquareRoot > input)
{
high = mid;
}
else
{
low = mid;
}
}
System.out.println(“Square root of “+input +” is between “+start +” and “+end + ” AND RESULT IS: “+result);
return 0;
}
}
