Last Updated: February 25, 2016
·
716
· saurabhksingh

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;

}

}