I need some help with the following question:
Let $S=${$x_1$,... $x_n$} be a set of $n$ real numbers listed in ascending order: $x_1<x_2<...<x_n$. Given a real number $r$ that exists in $[x_1,x_n]$\S, what is the fewest number of questions to ask to determine the subinterval $[x_i,x_{i+1}]$ that $r$ is in.
I know there are n-1 intervals that exist. So would the answer be $\log_2$(n-1)?
Assuming $r$ is uniformly distributed over $[x_1,x_n]\backslash S$.
Let $p_i = \frac{x_{i+1}-x_i}{x_n-x_1}$, for $i=1,2,\dots,n-1$. Then $\{p_i\}$ defines the probability distribution $p$ of which interval $r$ lies in. Then the minimum average number of questions one should ask to determine the interval is simply given by the average codeword length of the Huffman code for this distribution, i.e., $\lceil H(p)\rceil$, where $H(\cdot)$ denotes the entropy. The optimal sequence of questions to ask is given by the corresponding Huffman tree; see this link for example.