I would like to write a program that guesses a number chosen by a person, by asking the person questions of the form "is your number greater than x?".

If the number is an integer of a limited size (say, 32 bits), then it is easy to guess using binary search - 32 questions are sufficient.

Now, suppose the person chooses a real number that is represented by a floating-point variable (e.g. float in C , which also uses 32 bits). There are finitely-many possible values of a float, so my program should still be able to guess the exact float selected by the person using a small number of questions. But, I am not sure how to do it using binary search, since the possible values of a float are not evenly spaced.

Question: how can I guess a float value using a small number of questions of the form "is your number greater than x"?

To make the question more concrete, suppose you are given a function bool is_greater_than(float x). How many calls to this function do you need in order to guess the number? Can it be done with only 32 calls?

CodePudding user response：

After checking sign you have to find exponent as soon as possible. For 32-bit floats there are 255 possible values of exponent (256th is reserved for special numbers). So at the first stage do binary search over exponent value. At most 8 steps (8 bits of exponent)

Then perform usual binary search with step halving to determine exact value of mantissa - at most 23 steps (23 bits of mantissa)

This approach allows to overcome not evenly spaced problem, but there is another one - user can (and almost definitely does) guess number without exact binary representation, so you have to use some epsylon tolerance (depending on exponent)