3.1.40 #
解答 #
顺序查找平均需要进行 $N/2$ 次比较，二分查找则是 $\lg N$ 次。
列出方程可以解出 N 的大小
$$ \begin {eqnarray*} 1000 \log_2 N &=& N / 2 \newline \log_2 N &=& N / 2000\newline \frac{\ln N}{\ln 2} &=& N/2000 \newline N &=& e^{\frac{\ln 2}{2000}N}\newline 1 &=& Ne^{-\frac{\ln 2}{2000}N}\newline N_1 = e^{-W(-\frac{\ln 2}{2000})}=1 &\ & N_2= e^{-W_{-1}(-\frac{\ln 2}{2000})}=29718\newline \newline \end {eqnarray*} $$
这个方程是一个超越方程，最后的结果中出现了朗伯 W 函数。
同理可以求得 10000 倍的 N=369939。
实验结果如下：
由于存在缓存优化，每次比较的耗时并不相同。
因此实际耗时并未达到预期，但比较次数是符合预期的。