《编程珠玑》 二分查找在大量数据中的使用(查找一个不在文件中的数据)

     《编程珠玑》第二章提到的问题A：
      给定一个包含32位整数的顺序文件，它至多包含40亿个这样的整数，并且次序是随机的。请查找一个此文件不存在的32位整数。

      当然，主存足够的话，我们可以使用上章提到的位图法，2^32二进制位，如果用bitset那会超过数组大小范围（即0x7fffffff），使用上章提到的int型数据转换，倒是可以实现。但是，如果内存有限，毕竟你无法一下就开辟536870912个B，太浪费资源了，不是吗？
假设，我们只有上百字节的可用内存空间，我们就要使用书中提到的二分查找法，具体原理这里不论述，下面是关键的部分：

	//每次循环将初始文件转化为个数较小的数据文件
    while (true)
    {
		s = k = 0;
		//读原始数据
		ifstream infile(data,ios::in|ios::_Nocreate);
		if (!infile)
		{
			cerr<<"open error!"<<endl;
			exit(1);
		}
		//分成两个较小文件
		ofstream outfile1("file1.text",ios::out);
		ofstream outfile2("file2.text",ios::out);
		if (!outfile1 || !outfile2)
		{
			cerr<<"open error!"<<endl;
			exit(1);
		}
		for (i = 0;i < n;++ i)                              //每次需读入所有数据 共n个
		{ 
			infile>>temp;                                    //read record number
			if (left <= temp && temp <= (left + right)/2)
			{
				s++;       //left range
			    outfile1<<temp<<" ";
			}
			else          //right range
			{
				k++;
				outfile2<<temp<<" ";
			}
		}
	    infile.close();
		outfile1.close();
		outfile2.close();
		//磁盘数据读完结束
		if (s < k)                                 //select the left side
		{
			right = (left + right)/2;
			//生成新的较小原数据文件
			ofstream outfile("temp.text",ios::out);
			ifstream infile("file1.text",ios::in|ios::_Nocreate);
			if (!outfile || !infile)
			{
				cerr<<"open error!"<<endl;
				exit(1);
			}
			for (int i = 0;i < s;++ i)
			{
				infile>>temp;
				outfile<<temp<<" ";
			}
			n = s;
			outfile.close();
			infile.close();
		}
		else
		{
			left = (left + right)/2;                 //select the right side
			//生成新的较小原数据文件
			ofstream outfile("temp.text",ios::out);
			ifstream infile("file2.text",ios::in|ios::_Nocreate);
			if (!outfile || !infile)
			{
				cerr<<"open error!"<<endl;
				exit(1);
			}
			for (int i = 0;i < k;++ i)
			{
				infile>>temp;
				outfile<<temp<<" ";
			}
			n = k;
			outfile.close();
			infile.close();
		}
		data = "temp.text";
		if (n < SIZE)
		{
			break;
		}
    }

上述过程，每次while循环，生成一个个数较小的一半，并作为下次while循环的原始文件，这样，顺序扫描的文件从n,n/2,n/4,n/8 ....方式递减，另外，为了找到足够多的文件，并考虑到内存空间限制，我们在结果文件足够小时（即内存有效空间内，程序中的SIZE），对得到的文件采用排序算法，查找到遗漏的数据，我们这里采用了上章中提到的位图表示法：

	bitset <SIZE*10> bits;
	int p = 0;
	ifstream infile("temp.text",ios::in|ios::_Nocreate);
	cout<<"between "<<left<<"  and  "<<right<<endl;
	for (int i = 0;i < n;++ i)
	{
		infile>>temp;
		bits.set(temp-left);
	}
	infile.close();

	//保存遗漏数据到result文件
	ofstream outfile("result2.text",ios::out);
	if(!outfile)
	{
		cerr<<"open error!"<<endl;
		exit(1);
	}
	for (int i = left;i < right;++ i)
	{
		if (!bits.test(i-left))
		{
			outfile<<i<<" ";
			p++;
		}
	}

实验中，原始数据，我们使用了前面提到的产生方法，在亿计数量级上的数据，我们大概花了5~6小时，有大概花了2~3小时找到了1000多个遗漏数据，运行内存使用控制在300KB内（任务管理器中）。

评论

1 楼 evagame 2010-08-02  

自己看书的时候为这个问题困惑过，看了楼主的文章，获得了思路，谢谢了
不过要指出的是
“我们在结果文件足够小时（即内存有效空间内，程序中的SIZE），对得到的文件采用排序算法，查找到遗漏的数据”

这个不是作者在书中这道题答案的本意，作者明确指出，这道题不需要运用排序算法来解决。

算法读取所有记录，将他们分为高位为1，以及高位为0两类放到不同文件里（用低位也可以），这个过程不需要多少工作内存，几十个byte足够。
　　　　
通过这次分拣，他就知道遗漏的数字在哪一堆，不需要排序。因为第32位为1的数字必定有2^31个，算法中必定有个计数器，做完跟2^31比较一下，比它小的话，那么遗漏的数字肯定就在这一堆。
依次类推二分

楼主可以根据这个思想再写个程序 :-)