<<算法导论>>习题4-2怎么做
题目如下：A[1...N]包含[0...n]中的所有整数数字except one，找出这个数字很简单，只要用一个辅助数组B[0...N]就可以找出少掉的这个数字，复杂度为O(n)，但是现在的问题是不可以直接读取A中的整数，因为A中的整数是以二进制存取的，唯一的操作就是取其中的第几位，比如说取第j位，这个操作花费一个常量时间。
要求证明:找出那个少掉的数字仍只需要复杂度O(n)。A以外的数字仍可以通过一个常量时间读取。
(不知道题目的意思不能直接读取A中的整数，是不是紧紧不能读取10进制，因为如果可以读取二进制的话，就可以对A中的N个数用异或的方法找出那个少的数了。)
(还有感觉中文版的翻得不是很好，有些地方有点含糊,比如说最后这句"A以外的数字仍可以通过一个常量时间读取"是要求我们证明的呢，还是给的一个已知条件呢，虽然我觉得应该是个已知条件)
[解决办法]
为方便叙述 假设N为（2的幂次-1）
对【1.。。N】每个元素分别取第一位
如果是0，就放左边；否则放右边。
如果是0.....N，则两边元素应该相等
但是由于少了一个数，所以必有一边少了一个元素（有上面的假设）
所以对少了元素的一边 取每个元素的第二位 重复上面的过程
直到找到某一边 该边原应该包含一个元素，但是其中的元素为空，这个元素就是丢失的那个
T（N）=T（N/2）+N----------O(N)
