int mySqrt(int x) {
// answer is within [p, q) bound(including p, q not included)
int p = 0, q=46341;
while(qp>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;
}
The most elegant binary search(c 3ms)

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; }

@JPBlack
Forint
type, the C standard only require that it has at least 16 bits.
ifint
is represented as 16 bits, thenq = 46341
will result in overflow.
ifint
is represented as 64 bits, thenq = 46341
is not enough to get the right answer forx = 2147580964 (46342 * 46342)
.
q = x
will overflow even whenint
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^311) 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 64bit int yet.
there's some reasons why compilers keeps it 32bit despite we enter 64bit world: Portability
plus int is read as "Integer". generally, 32bit is big enough.
in addition, c provide intXX_t.
I think int will not be enlarged to 64bit very soon.
Some old programmers like to store pointer in int, which will cause some problems.
But nowadays I seldom see one do this. There's intptr_t that define a integer same size as pointer.