問題： 某數組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個數。