问题:   某数组A[1..n]含有所有从0..n的所有整数,但其中有一个整数不在数组中,通过利用一个辅助数组B[0..n]来记录A中出现的整数,很容易在O(n)时间内找出所缺的整数。但在这个问题中,我们却不能由一个单一操作来访问A中的一个完整整数,因为A中元素是以二进制表示的。我们所能用的唯一操作就是“取A[i]的第j位”这个操作所花时间为常数。       证明:如果访问数组A中信息的唯一方式是这种单一位操作,仍能在O(n)时间内找出所缺的整数。A之外的任一完整整数仍然可以由一个单一操作来访问。【算法导论 中文版  P50  4-2】
       昨天晚上看算法导论看到了这一题,没有想多久,没想通。当时想的是把A中的每一个信息都逐个获取,但是复杂度是O(lgn),今天在网上看别人的博客,学会了这个方法。利用了二进制的特点。(后面的东西是修改了Jianxing的blog里的。地址http://gonewiththedream.spaces.live.com/blog/cns!4327B97AC534D77E!235.entry)

基本方法就是用二分法:
1, 遍历整数0到n的第一位,分成两个数组:P1[1] 和P0[1],分别代表第一位是1,0的数,并记录第一位是1的个数CountN,代价为O(n)
2, 遍历数组A[1...n]的第一位, 分成两个组:Q1[1]和Q0[1],分别代表第一位是1,0的数,并记录1的个数CountA,代价为O(n)
3, 比较CountN和CountA的值,结果可能有两种情况CountN = CountA,或者CountN = CountA + 1, 前者表明所缺数的第一位为0, 后者为1,代价为O(1)
4, 通过3的结果,随后我们可以在P1[1]和Q1[1](CountN>CountA,即缺少第一位为1的数)  或者 P0[1]和Q0[1](CountN=CountA,即缺少第一位为0的数)中的第2位中重复步骤1,2中的操作,记录数组P1[2]、P0[2]和CountN'及Q1[2]、Q0[2]和CountA'。代价为O(n/2)和O(n/2), 经过比较后可得到所缺数第二位是0还是1,决定接下来比较P1[2]和Q1[2]  或者 P0[2]和Q0[2],代价O(1)
5, 不断重复Ceiling(lg(n))次,最后即可找到所缺数总代价为2* (O(n) + O(n/2) + ... +O(n/pow(2, k))) + ... + O(1)) = 2* O(2n) = 4*O(n) = O(n)
当然这里忽略了一个问题,如果A中缺了一个,这应该是n-1个数,则多出来的那个数是什么呢,如果和其他数有重复,上面的方法就无效了,情况变得相当复杂。因此上面的只适用于多出的一个数为0,或者干脆就只有n-1个数。