Didactic Binary Search

Submit

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

By solving this problem, you can learn (or reconfirm) how to implement binary search.

The output is self-descriptive. Please read it and consider what is going on.

In this implementation, the lower boundary of the value range is inclusive
and the upper boundary is exclusive.
The initial value of the lower boundary is zero. The upper boundary is given
in the first line of the input.

Then you must make a query whether the value is in the lower half of the range.
The answer to the query, expressed as 1 for yes or 0 for no, is given in the
next line of the input.
Repeat the above until you can determine the value which is an integer.
You must ignore the remaining input that is just a garbage.

-- tails

Options

exec is denied

no deadline, the server will not save your submission

Sample input:_

1024
1
1
1
0
0
1
1
0
1
1
0
0
1

Sample output:

Now I know the value is not less than 0 but less than 1024.

Is the value less than 512?
Yes!
Now I know the value is not less than 0 but less than 512.

Is the value less than 256?
Yes!
Now I know the value is not less than 0 but less than 256.

Is the value less than 128?
Yes!
Now I know the value is not less than 0 but less than 128.

Is the value less than 64?
No!
Now I know the value is not less than 64 but less than 128.

Is the value less than 96?
No!
Now I know the value is not less than 96 but less than 128.

Is the value less than 112?
Yes!
Now I know the value is not less than 96 but less than 112.

Is the value less than 104?
Yes!
Now I know the value is not less than 96 but less than 104.

Is the value less than 100?
No!
Now I know the value is not less than 100 but less than 104.

Is the value less than 102?
Yes!
Now I know the value is not less than 100 but less than 102.

Is the value less than 101?
Yes!
Now I know the value is not less than 100 but less than 101.

That is, the value is 100.

Sample input:_

3456
1
0
1
0
0
1
0
0
1
0
0
0
1
0
0
0

Sample output:

Now I know the value is not less than 0 but less than 3456.

Is the value less than 1728?
Yes!
Now I know the value is not less than 0 but less than 1728.

Is the value less than 864?
No!
Now I know the value is not less than 864 but less than 1728.

Is the value less than 1296?
Yes!
Now I know the value is not less than 864 but less than 1296.

Is the value less than 1080?
No!
Now I know the value is not less than 1080 but less than 1296.

Is the value less than 1188?
No!
Now I know the value is not less than 1188 but less than 1296.

Is the value less than 1242?
Yes!
Now I know the value is not less than 1188 but less than 1242.

Is the value less than 1215?
No!
Now I know the value is not less than 1215 but less than 1242.

Is the value less than 1228?
No!
Now I know the value is not less than 1228 but less than 1242.

Is the value less than 1235?
Yes!
Now I know the value is not less than 1228 but less than 1235.

Is the value less than 1231?
No!
Now I know the value is not less than 1231 but less than 1235.

Is the value less than 1233?
No!
Now I know the value is not less than 1233 but less than 1235.

Is the value less than 1234?
No!
Now I know the value is not less than 1234 but less than 1235.

That is, the value is 1234.

Sample input:_

7777
0
1
0
0
1
0
0
1
0
0
0
1
0
1
0
0
1
0

Sample output:

Now I know the value is not less than 0 but less than 7777.

Is the value less than 3888?
No!
Now I know the value is not less than 3888 but less than 7777.

Is the value less than 5832?
Yes!
Now I know the value is not less than 3888 but less than 5832.

Is the value less than 4860?
No!
Now I know the value is not less than 4860 but less than 5832.

Is the value less than 5346?
No!
Now I know the value is not less than 5346 but less than 5832.

Is the value less than 5589?
Yes!
Now I know the value is not less than 5346 but less than 5589.

Is the value less than 5467?
No!
Now I know the value is not less than 5467 but less than 5589.

Is the value less than 5528?
No!
Now I know the value is not less than 5528 but less than 5589.

Is the value less than 5558?
Yes!
Now I know the value is not less than 5528 but less than 5558.

Is the value less than 5543?
No!
Now I know the value is not less than 5543 but less than 5558.

Is the value less than 5550?
No!
Now I know the value is not less than 5550 but less than 5558.

Is the value less than 5554?
No!
Now I know the value is not less than 5554 but less than 5558.

Is the value less than 5556?
Yes!
Now I know the value is not less than 5554 but less than 5556.

Is the value less than 5555?
No!
Now I know the value is not less than 5555 but less than 5556.

That is, the value is 5555.

Ranking

Ruby _

Ruby2 _

Perl _

Python _

Python3 _

JavaScript _

Lua _

C _

Java _

bc _

Scala _

Language Ranking_

return to the top page