问题描述：有两份文件，一份包含100W个数字（largeW.txt)，作为白名单，另一份含1000W个数字(largeT.txt)，如果此数字存在于白名单中，则不处理，如果不在，则打印出来。
要求：
a）使用二分查找；
b）计算程序运行时间；
c）数据采用rand.cc自动生成。
1、将100W个int数据，和1000W个int数据分别存放于samllT.txt 和 largeT.txt中，
rand.cc程序比较简单，代码如下：
<br>//radn.cc -->生成随机数
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <unistd.h>
#include <errno.h>
#include <sys/time.h>
#define ERR_EXIT(m) \
do { \
perror(m);\
exit(EXIT_FAILURE);\
}while(0)
using namespace std;
<br>//写入文件
void writeIntegerToFile(int fd, int value)
{
char text[100] = {0};
snprintf(text, sizeof text, "%d\n", value);
if(write(fd, text, strlen(text)) == -1)
ERR_EXIT("write");
}
//返回time
double get_time() // 对运行时间进行封装
{
struct timeval tm;
memset(&tm, 0, sizeof tm);
if(gettimeofday(&tm, NULL) == -1)
ERR_EXIT("gettimeofday");
double res = 0.0;
res += tm.tv_sec;
res += tm.tv_usec / (double)1000000;
return res;
}
int main(int argc, const char *argv[])
{
double startTime = get_time();
const int kSize = 1000000;
srand(kSize);
int fd = open("largeT.txt", O_CREAT | O_WRONLY | O_TRUNC, 0666);
if(fd == -1)
ERR_EXIT("open");<br>
for(int i = 0; i != kSize; ++i)
{
writeIntegerToFile(fd, rand() % kSize);
}
close(fd);<br>
double endTime = get_time();
double cost = endTime - startTime;
cout << "花费时间 " << cost << " s" << endl;
return 0;
}2、二分查找算法：
注意：二分查找通常用在已经有序的数组中。
解法：
1）：通过下标操作， 我们把要查找的元素值记为 val ，首元素的下标记为 low， 末尾元素的下标记为high； mid 为low 和 high 的中间值 ，即 mid = （high+low）/2 ；
2）： 比较 val 与mid 所对应的元素值
3）：如果 val 等于 当前的 mid 所对应的元素值 ，则查找成功 ；
4）： 如果 val 大于 当前的mid 所对应的元素值， 则说明 我们要查找的元素 （可能）位于后半段 ；我们将当前的mid值 赋值给 low ，再将mid 的下标置为（low +high）；执行 步骤 2）。
5）： 如果 val小于 当前的mid 所对应的元素值， 则说明 我们要查找的元素 （可能）位于前半段 ；我们将当前的mid值 赋值给 high ，再将mid 的下标置为（low +high）；执行 步骤 2）。
6）：若当 low 的值 大于high 的值时 ，仍未找到该val ，则说明查找失败 。
代码如下：
//BinarySearch.cc
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
#include <sys/time.h>
#include <algorithm>
using namespace std ;
bool BinarySearch(const vector<int> vec , int val, int min, int max)
{
int mid = (min + max )/2 ;
while( min <= max )
{
if(vec[mid] == val )
{
return true ;
}else if( vec[mid] > val )
{
max = mid - 1 ;
mid = (min + max) / 2 ;
}else
{
min = mid + 1 ;
mid = (min + max ) / 2 ;
}
}
cout << "The val of the num is :" << val << " " << endl ;
return false ;
}
int main(int argc, const char *argv[])
{
FILE* fpLarge = fopen("largeT.txt" , "rb") ;
FILE* fpSmall = fopen("smallT.txt" , "rb") ;
if(NULL ==fpLarge || NULL == fpSmall)
{
perror("open");
exit(1);
}
vector<int> Larvec ;
vector<int> Smlvec ;
// int Ssize = 10000 ;
int Lsize = 1000000 ;
char buf[128] ;
while(memset(buf , 0, sizeof(buf)) ,fgets(buf ,sizeof(buf) ,fpLarge)!= NULL)
{
int tmp = atoi(buf);
Larvec.push_back(tmp);
}
sort( Larvec.begin() , Larvec.end());
int val ;
while(memset(buf , 0, sizeof(buf)) ,fgets(buf ,sizeof(buf) ,fpSmall)!= NULL)
{
val = atoi(buf);
Smlvec.push_back(val);
}
int cnt = 0 ;//标记未查找成功的个数
for(vector<int>::size_type ix = 0 ; ix != Smlvec.size() ; ++ix)
{
bool rec ;
rec = BinarySearch(Larvec , Smlvec[ix], 0 , Lsize );
if(!rec)
cnt ++ ;
}
cout << "The cnt of Searching false is : " << cnt << endl ;//输出查找失败总数
cout << "Time used = " << (double)clock()/CLOCKS_PER_SEC << endl ;//输出程序运行时间
fclose(fpLarge);
fclose(fpSmall);
return 0;
}
本文含有隐藏内容，请 开通VIP 后查看