How to guess the age in the least number of attempts?

Question

Algorithms

We have a population of people from one to a hundred years old, and we know in advance the approximate statistics of the distribution of people by age. How, in the least number of steps, to "guess" the age of a person, if he can only be asked questions in the format "Are you older/younger than N years?". I know how to guess in 7 steps (using the bisection method), but I'm interested in more advanced methods. I would be grateful for any thoughts on this.

Answer 1

Binary search, but the division point is not (a+b)/2, but the median of the distribution piece from a to b (i.e. round(F ⁻¹ ([F(a) + F(b)]/2)) ; F(·) is a distribution function, stupidly converted from a piecewise constant form into a piecewise linear, spline, or some other).
A little suboptimal, but extremely simple.
Z.Y. This thing is quite optimal for "smooth" distributions. In the general case, it is not optimal - for example, if we have three ages with probabilities of 0.45, 0.1 and 0.45, it is worth asking the first, then the third, and even with complete bad luck the second (average 1.65 of the request), and not taking the average , and then the first or second (average 1.9 requests).
If you need an exact optimum, solve the dynamic programming problem according to the criterion
N[a,b] = min{c} (1 + (N[a,c−1]p[a,c−1] + N[c+1,b]p[c+1,b]) / p[a,b]).
Boundary conditions: for a = b N[a,b] = 1; for a>b N[a,b] = 0.
p[a,b] is the total probability from a to b inclusive; computed as sum[b]−sum[a−1]; sum[i] = sum{x <= i} p(x).
N[0,M] = ?
Or, denoting Q[a,b] as N[a,b]p[a,b],
Q[a,b] = min{c} (p[c] + Q[a,c−1] + Q [c+1,b]).
Since p[0,M] = 1, then Q[0,M] = N[0,M].
Boundary conditions: for a = b Q[a,b] = p[a]; for a>b Q[a,b] = 0.
Q[0,M] = ?
The problem is solved in O(M²) operations. If you need to store all the information in order to scroll through the chain of requests at the right time - O (M²) memory; if you only specify the optimum, you can get by with O(M).

Answer 2

IMHO, for an accurate result - only a binary search, as you do.
All other methods are results with probability.

Answer 3

Try dividing by three)
Well, it would be nice to use distribution statistics to increase the chances.