“《编程珠玑》（第2版）第2章”：A题（二分搜索）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

A题是这样子的：

给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺失一个这样的数据——为什么？）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几个字节的内存，又该如何解决该问题？

因为2^32>40亿，所以，在文件中至少会缺少一个这样的数据。在有足够内存的情况下，我们可以使用上一章提到的位图数据结构来解决该问题。但利用位图数据结构来解决该问题需要利用到的内存为：40亿/8/1024/1024=476MB，所以当内存不足时是不能够用这种方法的。

前面一篇博文提到了可以用数列求和方法来求得缺失的数。但就是这种方法有一个要求就是，任一个数与其前一个数的差值是一个定值，即要求该数列是一个等差数列。所以，如果我们能够确定，这个需要找出缺失的数的顺序文件里边的数是一个等差数列，那我们就可以利用该方法简单求出缺失的数了，而且占用内存极少，效率当然也就更高。

作者对该问题的解决方法是利用“二分搜索”的方法。具体如下：

算法的第一趟（最多）读取40亿个输入整数，并把起始位为0的整数写入一个顺序文件，把起始位为1的整数写入另一个顺序文件。如下图所示。

这两个文件中，有一个文件最多包含20亿个整数，我们接下来将该文件用作当前输入并重复探测过程，但这次探测的是第2个位。如果原始的输入文件中包含n个元素，那么第1趟将读取n个整数，第2趟最多读取n/2个整数，第3趟最多读取n/4个整数，依此类推，所以总的运行时间正比于n。通过排序文件并扫描，我们也能够找到缺失整数，但是这样做会导致运行时间正比于nlogn。

下边我们就来看看，用“二分搜索”怎么解决这个问题：

1. 文件读写

首先我们来看怎么进行文件的读写。有一篇博文总结的很不错，值得参考。贴出具体代码如下：

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <math.h>
using namespace std; int main()
{
// *************************** Write File *************************** //
// Open file
ofstream wfile("file.txt", ios::out);
if (!wfile)
{
cout << "The file can not be opened!" << endl;
exit();
} for (int i = ; i < pow(, ); i++)
{
stringstream ss;
ss << i;
string str = ss.str();
wfile << str;
wfile << endl;
} // Close the file
wfile.close(); // *************************** Read File *************************** //
// Open file
ifstream rfile("file.txt", ios::in);
if (!rfile)
{
cout << "The file can not be opened!" << endl;
exit();
} string line;
int num;
while (getline(rfile, line))
{
// cout << line << endl;
stringstream ss;
ss << line;
ss >> num;
cout << num << endl;
} // Close the file
rfile.close(); return ;
}

2. 实际操作

生成40亿个数据实在是太庞大了，因此在这里我选择了生成0~65535个顺序数列，然后随意去掉一个数，检验程序能否找出缺失的数。

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <math.h>
using namespace std; typedef unsigned int uint; int main()
{
//// *************************** Write File *************************** //
//// Open file
//ofstream wfile("file.txt", ios::out);
//if (!wfile)
//{
// cout << "The file can not be opened!" << endl;
// exit(1);
//} //for (int i = 0; i < pow(2, 16); i++)
//{
// stringstream ss;
// ss << i;
// string str = ss.str();
// wfile << str;
// wfile << endl;
//} //// Close the file
//wfile.close(); // *************************** Read File *************************** //
// Open file
ifstream rfile("file.txt", ios::in);
if (!rfile)
{
cout << "The file can not be opened!" << endl;
exit();
} vector<uint> right, left;
string line;
uint num;
while (getline(rfile, line))
{
// cout << line << endl;
stringstream ss;
ss << line;
if (line != "")
{
ss >> num;
if (num & ( << ))
right.push_back(num);
else
left.push_back(num);
} }
// Close the file
rfile.close(); uint count = ;
uint miss = ;
uint szLeft = ;
uint szRight = ;
while (count != )
{
vector<uint> temp;
szLeft = left.size();
szRight = right.size(); if (szLeft < szRight)
{
right.clear();
for (uint i = ; i < szLeft; i++)
{
if (left[i] & ( << - count))
right.push_back(left[i]);
else
temp.push_back(left[i]);
}
left.clear();
left = temp;
}
else
{
left.clear();
for (uint i = ; i < szRight; i++)
{
if (right[i] & ( << - count))
temp.push_back(right[i]);
else
left.push_back(right[i]);
}
right.clear();
right = temp;
} count++;
} szLeft = left.size();
szRight = right.size();
if (szLeft > szRight)
{
miss = left[] + ;
}
else if (szLeft < szRight)
{
miss = right[] - ;
}
else
{
// no elements is missed
miss = ;
} cout << "The missed one is: " << miss << endl; return ;
}

注：该程序实际所占内存还是挺大的（针对存有40亿个数据的文件），主要是在前期刚从文件读入数据的时候。作者提到的是把这些中间数据写到文件中去的方法，但我在这里为了便于处理，就没有将中间数据写出然后再读进来。当然，我这样做只是权宜之计，要实际解决内存不足的话还是得将中间数据写出文件然后再读取。

通过不断地二分，因为缺少一个整数，所以程序中left和right的大小至少一个为0，又因为，最后的left和right（都已经只有一个数）如果在没有缺失数的情况下，有left[0] = right[0] - 1，这样就很简单就能够判断出缺少的是哪一个数了。

当然程序是可以找出缺失的数的。因为只是验证一下算法，程序的健壮性是没有太多考虑的。

我们可以看到，“二分法”能让程序对时间和空间的需求呈指数级下降，效果是特别明显的。

注：后来又看到其他人的想法，此程序的效率还是可以继续提升的！

我们每次读入总数1/10的数据量的时候，就比较一下最后一个读入的数据D_last跟读入的数据量大小L_read：

如果D_last＋１＝L_read，则表明目前读入的数据中并没有缺失的数，也因此可以在后边将二分搜索起点设定为L_read；
如果D_last＝L_read，则表明目前已经读入的数据就已经存在缺失的数了，也就是说不用再继续读入数据了。

3. 课后习题2

给定包含4 300 000 000个32位整数的顺序文件，如何找出一个出现至少两次的整数？

二分搜索通过递归搜索包含半数以上整数的子区间来查找至少出现两次的单词。因为4300000000 > 2^32，所以必定存在重复的整数，搜索范围从[0, 2^32）开始，中间值mid为2^31，若区间[0, 2^31)内的整数个数大于2^31个，则调整搜索区间为[0, 2^31)，反之则调整搜索区间为[2^31， 2^32)，然后再对整个文件再遍历一遍，直到得到最后的结果。

在这里我选择了生成0~65535个顺序数列，然后随意增加N个重复的数，检验程序能否找出重复的数。程序如下：

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <math.h>
using namespace std; typedef unsigned int uint; int main()
{
//// *************************** Write File *************************** //
//// Open file
//ofstream wfile("file.txt", ios::out);
//if (!wfile)
//{
// cout << "The file can not be opened!" << endl;
// exit(1);
//} //for (int i = 0; i < pow(2, 16); i++)
//{
// stringstream ss;
// ss << i;
// string str = ss.str();
// wfile << str;
// wfile << endl;
//} //// Close the file
//wfile.close(); // *************************** Read File *************************** //
// Open file
ifstream rfile("file.txt", ios::in);
if (!rfile)
{
cout << "The file can not be opened!" << endl;
exit();
} vector<uint> right, left;
string line;
uint num;
while (getline(rfile, line))
{
// cout << line << endl;
stringstream ss;
ss << line;
if (line != "")
{
ss >> num;
if (num & ( << ))
right.push_back(num);
else
left.push_back(num);
} }
// Close the file
rfile.close(); uint count = ;
uint repeat = ;
uint szLeft = ;
uint szRight = ;
while (count != )
{
vector<uint> temp;
szLeft = left.size();
szRight = right.size(); if (szLeft > szRight)
{
right.clear();
for (uint i = ; i < szLeft; i++)
{
if (left[i] & ( << - count))
right.push_back(left[i]);
else
temp.push_back(left[i]);
}
left.clear();
left = temp;
}
else
{
left.clear();
for (uint i = ; i < szRight; i++)
{
if (right[i] & ( << - count))
temp.push_back(right[i]);
else
left.push_back(right[i]);
}
right.clear();
right = temp;
} count++;
} szLeft = left.size();
szRight = right.size();
if (szLeft > szRight)
{
repeat = left[];
}
else if (szLeft < szRight)
{
repeat = right[];
}
else
{
// no elements is repeated
repeat = ;
} cout << "The repeated one is: " << repeat << endl; return ;
}