Бинарный поиск, однако точка деления — не (a+b)/2, а медиана куска распределения от a до b (т.е. round(F−1([F(a) + F(b)]/2)); F(·) — функция распределения, тупо переделанная из кусочно-постоянного вида в кусочно-линейный, сплайновый или ещё какой-нибудь).
Немного неоптимально, но крайне просто.
З.Ы. Эта штука достаточно оптимальна для «гладких» распределений. В общем случае неоптимальна — например, если у нас три возраста с вероятностями 0,45, 0,1 и 0,45, стоит спросить первый, потом третий и уж при полном невезении второй (среднее 1,65 запроса), а не брать среднее, а затем — первое или второе (в среднем 1,9 запросов).
Если нужен точный оптимум — решать задачу динамического программирования по критерию
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]).
Граничные условия: при a = b N[a,b] = 1; при a>b N[a,b] = 0.
p[a,b] — суммарная вероятность от a до b включительно; вычисляется как sum[b]−sum[a−1]; sum[i] = sum{x <= i} p(x).
N[0,M] = ?
Или, обозначив Q[a,b] как N[a,b]p[a,b],
Q[a,b] = min{c} (p[c] + Q[a,c−1] + Q[c+1,b]).
Так как p[0,M] = 1, то Q[0,M] = N[0,M].
Граничные условия: при a = b Q[a,b] = p[a]; при a>b Q[a,b] = 0.
Q[0,M] = ?
Решается задача за O(M²) операций. Если нужно хранить всю информацию, чтобы в нужный момент прокрутить цепь запросов — O(M²) памяти; если только указать оптимум — можно обойтись O(M).
Средний
Простой
Средний
