Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
public class Sqrt{
public int sqrt(int x){
if(x == 0 || x == 1) return x;
int low = 1;
int high = x;
int mid = 0;
while (low <= high){
mid = low / 2 + high / 2; // to further avoid low + high causing integer overflow
// here we do use the (mid*mid <= x) && ((mid+1)^2 > x)
// we can also use a different one: mid*mid > x - 2*mid - 1 and mid*mid <= x
// the difference between mid^2 and (mid+1)^2 is 2*mid + 1
// if ((mid > (x - 2 * mid - 1) / mid) && (mid <= x / mid)) break;
if((mid <= x / mid) && (mid + 1 > x / (mid + 1))) break;
else if (mid > x / mid) high = mid - 1;
else low = mid + 1;
}
return mid;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment