## 基于算数编码的二分查找进行压缩的期望查询次数证明 (from @zhangmeng)

在区间$[0,1]$上，进行区间$[x, x+p]$的二分查找，即查找位置落在区间内即停止。假设每次二分查找后的方向都正确，$x\in[0,1-p]$均匀分布，易证，查找次数存在上限 $n$：
$$
\frac{1}{2^{n-1}} < p \leq \frac{1}{2^{n}} \\
n = \lfloor-\log{p}\rfloor + 1
$$
考虑标准的二分查找点位$\frac{1}{2},\frac{1}{4},\cdots$，对于区间$[x, x+p]$，进行二分查找时存在两种情况：

1. $\frac{i-1}{2^{n-1}} \leq x < \frac{i}{2^{n-1}}-p$ ，此时必定二分$n$次才能落到区间内；
2. $\frac{i}{2^{n-1}}-p \leq x < \frac{i}{2^{n-1}}$，对于所有$2^{n-1}-1$个查找点位，查找1次的有$2^0$个($\frac{1}{2}$)，查找2次的有$2^1$个($\frac{1}{4}$，$\frac{3}{4}$)，……，查找$n-1$次的有$2^{n-2}$个。（可以通过将$i$转化为二进制表示证明）

那么，对于区间$[x, x+p]$，$x\in[0,1-p]$为均匀分布，二分查找次数的期望为：

$$
\begin{align}
E &= \frac{1}{1-p}(n*(\frac{1}{2^{n-1}}-p)*2^{n-1} + \sum_{i=1}^{n-1} 2^{n-2}*(n-1)*p) \\
&= \frac{1}{1-p}(n*(1-p*2^{n-1}) + [(n-2)*2^{n-1}+1]*p)\\
&= \frac{1}{1-p}(n - (-2^n+1)p)
\end{align}
$$

举例测试，不妨设$p=\frac{1}{3}$， $x\in[0,\frac{1}{6}]$时查找2次， $x\in[\frac{1}{6},\frac{1}{2}]$时查找1次， $x\in[\frac{1}{2},\frac{1}{3}]$时查找2次，$E = \frac{3}{2}$，此时$n=2$，与公式相符。

当p较小时，$E\propto n$。