//binary search
int mySqrt(int x) {
if(x == 0)
{
return 0;
}
int left = 1, right = x;
int mid = (left + right)/2;
while(true)
{
if(x/mid > mid)
{
if((x/mid  mid) == 1)
{
return mid;
}
left = mid;
mid = (left + right)/2;
}else if(x/mid < mid)
{
if((mid  x/mid) == 1)
{
return x/mid;
}
right = mid;
mid = (left + right)/2;
}else
{
return mid;
}
}
}
My C code accepted with 5 ms


The algorithm is great, the following is refactor of it, for readability:
int mySqrt(int x) { if (x <= 0) return 0; int a = 1; int b = (x == INT_MAX) ? (x  1) : x; // avoid overflow while (a < b) { if (b  a == 1) return a; int m = (a + b) / 2; int d = m  (x / m); if (d == 0) return m; if (d < 0) a = m; else b = m; } return a; }
Further improvements are welcome!