If `x`

has `n`

binary digits, the square root of `x`

contains `m = floor((n + 1) / 2)`

digits, and then binary search among numbers of `m`

digits. Speed seems to be stable at 3ms comparing with 3~6ms of pure binary search.

```
int mySqrt(int x)
{
int d = binaryDigits(x);
if (d == 0) return 0;
d = (d + 1) / 2;
int l = power(2, d - 1);
int r = l * 2 - 1;
int mid;
while (l < r) {
mid = (l + r) / 2;
if (power(mid, 2) <= x)
if (power(mid + 1, 2) > x)
return mid;
else
l = mid + 1;
else
r = mid - 1;
}
return l;
}
int binaryDigits(int n)
{
int i = 0;
for (; n > 0; n /= 2, i++);
return i;
}
long power(int b, int p)
{
long i = 1;
while (p-- > 0) i *= b;
return i;
}
```