Algorithm selection

[Builder_1]

if i were asked a secret question between 1 and 1 billion by asking yes/no question of the form "is the number less than X?
" what algo should i use to efficiently find the secret number?
using the algo what will be the minimum number of questions if asked will guarantee to find
the secret number???

[Moschops]

You can make it easier to think about by pretending the number is between one and ten. The algorithm is identical.

[JamesCherrill]

Just think of the number in in its binary representation.
What question will tell you the value of the first bit?
Knowing that, what question will tell you the value of the next bit?
How many questions will you need to know the values of all the bits?

[umairs007]

It will be Binary Search
And Also 1000000 = 2^30
So Questions will be Log(2^30) = 30

[Builder_1]

cant it be done with recursion... and 2^30 is 1000000000 not 1000000

[Builder_1]

kindly someone to guide that instead of binary search..cant it be done with recursion???

[SalmiSoft]

A binary search may be implemented using recursion. Take a look at
http://rosettacode.org/wiki/Binary_search#C.2B.2B