理论计算机(I)课上讲的一个问题，很有意思。
已经一个 n ， m 和$ \{1,2,\cdots, m\}$ 里 n 个数，设计一种保存这 n 个元素的表的数据结构形式，使得对$ \{1,2,\cdots, m\}$ 中任何一个数，可以最少的查询次数（每次查询，可以选择一个位置，然后你能知道表中这个位置的数据），获知这个数是否在表中。
如果设计这个表为有序表，用二分法需要$ \log n$ 次查询。
有序表是最优的么？
举一个例子，一个保存 1 ， 2 ， 3 里面的两个数的有序表，要想知道 2 是否在这个表里面，至少需要两次查询。可不可以用一种特定的数据结构，使得一次查询就能判定任何一个数是不是在数据库里面？
结论是可能的，见下图：
一般的，假如表里的 n 个数的范围是 1 ， 2 ，...， 2n-2 ，即$ m=2n-2$ ，可以设计一种方法，使得，对于任何一个数，只需要查询一次，便能知道这个数是否在这个表里面。
课堂上有同学当场就想出设计方法，向他致敬！
另外，利用广义的 Ramsey 定理，对于固定的 n ，能够证明当 m 足够大时，无论你怎么设计那个表的结构，也至少需要$ \log n$ 的查询次数。
一个很神奇的问题。相关论文Should Table be Sorted?, 上面的图片也来自这篇文章。
Q. E. D.
