There is a box, you need to find out what’s in the box?
You know that is one out of n things - thing #1, thing #2 …. thing #n
$Thing_i$ occurs with a probability $p_i$
What is the average number of binary questions in worst case you need to ask to find out what’s in the box.
lets say there are each “n” thing occurs with the same probability(1/n), then how many binary questions would be required to find out the right thing?
Naive approach
Is it thing #1
Is it thing # 2
..
and so on.
In the above method, the luckiest case is 1. You guess randomly and ask if its in the box or not. And its there, no more questions.
But in the worst case, it is n - 1, once you have asked you know its not n- 1 questions, you know its the remaining one in the box.
But can we do better. Its is better to translate this to classic computer science 101 problem, if you have an array of n sorted numbers, how do you find your required number?
Naive algorithm says check if each element of array matches your required number or not. This is just like the naive approach.