阅读《编程珠玑》遇到的问题1：给定包含4300 0000 000个32位整数的顺序文件，如何找出出现至少两次的整数？

Question

阅读《编程珠玑》遇到的问题1：给定包含4300 0000 000个32位整数的顺序文件，如何找出出现至少两次的整数？
该题来自《编程珠玑》第二章课后习题第2题，课后给出的答案如下所示，但是这个答案我没有看懂， 求解惑。

疑问：顺序文件可以随机访问吗？我想访问第10个整数，就必须要从得先访问第1个、第2个、、第9个吗？

• 如果支持随机访问的话，我们可以用二分法对这个顺序文件进行搜索，时间复杂度应该为log(n)，空间复杂度为O(1)， 我就只需把我们随机访问的数放在内存里就可以了。

• 如果不可以随机访问的话，那么我们就一次遍历这个顺序文件，检查相邻两个元素的是否相等，就可以找到找到一个至少出现两次的整数了。而且每次我们只需要将当前访问的数放在内存中，故空间复杂度应该为O(1)，时间复杂度为O(n)。

但是从课后给出的答案来看，我的想法应该是有问题的。

Answer 1

后来发现，我读错题了。顺序文件并不是说这4300 000 000 000个整数按照从小到大的顺序排列的，
它只是说由一些系列的记录由某种顺序排列而成的文件，一般来说这些记录都是定长的。

解决方案：

• 二分搜索通过递归搜索包含半数以上整数的子区间来查找至少出现两次的单词。

• 搜索的区间： [left, right], 此时data数组中的所有数的范围都在[left, right]中，而数组中数的数量 > (right - left + 1)

• middle = (left + right) / 2

• 搜索data，将它分成两个数组，一个数组中所有的数 <= middle, 一个数组中的所有数都 > middle
  （注意，此处分成的数组并不是对半分的，可以一个数组里什么都没有，一个数组里包含了所有，再一次搜索的时候我们还要遍历相同规模的数据，复杂度将为nlog n）

• 选择包含半数以上的区间，接着如上方式搜索。

• 当left ==right时，此时此时data数组中的所有数的范围都在[left, right]中，即都为left, 而数组中数的数量 > 1, 故此我们找到了一个至少出现两次的整数。

初始条件：

• 搜索区间[-2^31, 2^31-1]
• data区间都是32位整数，所以范围在[-2^31, 2^31-1], 数量为4300 000 000 000，比2^32大。

改进：

• 上述方案的时间复杂度为 nlog n。主要是因为我们在将一个data数组根据middle划分为两个数组时，一个数组
  中的数量可能过多导致的。

• 我们其实不需要将整个数组都遍历一遍，只要遍历到第(right - left + 2）个就可以了，这里面一定存在重复值。可以缩短我们每次的遍历时间，降低时间的复杂度。