# The most elegant binary search(c 3ms)

• ``````int mySqrt(int x) {
// answer is within [p, q) bound(including p, q not included)
int p = 0, q=46341;
while(q-p>1) {
int mid = (p+q)/2;
if(mid*mid <= x)
p = mid;
else
q = mid;
}
// here [p, p+1), so answer is p
return p;
}
``````

• very neat code!

• I am not quite sure whether `q = 46341` is a good idea.
Instead of using multiplication, division can avoid the overflow.

``````int mySqrt(int x) {
int l = 1, r = INT_MAX;
while (l != r - 1) {
int m = l + (r - l) / 2;
if (x / m >= m) l = m;
else r = m;
}
if (x / l >= l) return l;
return l - 1;
}
``````

• Why use `q = 46341`? Why not `q = x`? This should save quite a few steps.

• @JPBlack
For `int` type, the C standard only require that it has at least 16 bits.
if `int` is represented as 16 bits, then `q = 46341` will result in overflow.
if `int` is represented as 64 bits, then `q = 46341` is not enough to get the right answer for `x = 2147580964 (46342 * 46342)`.
`q = x` will overflow even when `int` is 32bits.

• @FindRX Thank you. I might have to look into C a bit more – I haven't done much with it, yet.

• @JPBlack
I am using sqrt(2^31-1) here. yap, q=x will be faster by few steps. yet the complexity is still constant
note that q is not included, it is q=x+1, otherwise mySqrt(1) will be wrong.

@FindRX
Spec says that BITS(long)>=BITS(int)>=BITS(short)
I've not seen 64-bit int yet.
there's some reasons why compilers keeps it 32-bit despite we enter 64-bit world: Portability
plus int is read as "Integer". generally, 32-bit is big enough.