int l = 0;
int r = 1000;
int x = 1000;
// l and r denote our current bounds: we know that l <= x <= r
while(l<r) {
// we will ask about the number in the middle
int m = (l+r)/2;
// note: this is an integer division, thus e.g., for l=0, r=1 we get m=1/2=0
if(x <= m)
r = m;
else
l = m+1;
}
aW50IGwgPSAwOwppbnQgciA9IDEwMDA7CmludCB4ID0gMTAwMDsKLy8gbCBhbmQgciBkZW5vdGUgb3VyIGN1cnJlbnQgYm91bmRzOiB3ZSBrbm93IHRoYXQgbCA8PSB4IDw9IHIKd2hpbGUobDxyKSB7CiAgLy8gd2Ugd2lsbCBhc2sgYWJvdXQgdGhlIG51bWJlciBpbiB0aGUgbWlkZGxlCiAgaW50IG0gPSAobCtyKS8yOwogIC8vIG5vdGU6IHRoaXMgaXMgYW4gaW50ZWdlciBkaXZpc2lvbiwgdGh1cyBlLmcuLCBmb3IgbD0wLCByPTEgd2UgZ2V0IG09MS8yPTAKICBpZih4IDw9IG0pCiAgICByID0gbTsKICBlbHNlCiAgICBsID0gbSsxOwogIH0=