首页 > 代码库 > C++学习之二分查找续
C++学习之二分查找续
本文主要对上篇博文的 main函数 进行封装。
随机生成数据rand.cc 见上篇博文。
封装为函数及其各自的作用如下：
//读取数据到vecvoid readfile(const string &filename , vector<int> &vec);//二分查找bool BinarySearch(const vector<int> &vec , int val);//暴力查找bool SimpleSearch(const vector<int> &vec , int val) ;//查找数据 并打印出未在白名单里的数据以及这些数据的总和。 int findandprint(const vector<int> &white , const vector<int> &data );//程序运行时间int64_t getTime();
完整代码如下：
1 #include <iostream> 2 #include <string> 3 #include <vector> 4 #include <algorithm> 5 #include <string.h> 6 #include <sys/time.h> 7 #include <stdio.h> 8 #include <stdlib.h> 9 #include <string.h> 10 #include <algorithm> 11 using namespace std ; 12 13 //读取数据到vec 14 void readfile(const string &filename , vector<int> &vec); 15 //二分查找 16 bool BinarySearch(const vector<int> &vec , int val); 17 //暴力查找 18 bool SimpleSearch(const vector<int> &vec , int val) ; 19 //查找数据 并打印出未在白名单里的数据以及这些数据的总和。 20 int findandprint(const vector<int> &white , const vector<int> &data ); 21 //程序运行时间 22 int64_t getTime(); 23 24 25 int main(int argc, const char *argv[]) 26 { 27 //读取white数据到文件 28 //读取testcase 数据至文件 29 //对whitecase排序 30 //查找测试数据 31 if(argc < 3) 32 { 33 fprintf(stderr , "Usage :%s , white ,testcase\n", argv[0]); 34 exit(EXIT_FAILURE); 35 } 36 int64_t starttime = getTime(); 37 38 vector<int> white ; 39 vector<int> testcase ; 40 string whiteFile = argv[1]; 41 string testFile = argv[2]; 42 43 readfile(whiteFile ,white); 44 readfile(testFile , testcase); 45 46 sort(white.begin() , white.end()); 47 48 int cnt = findandprint(white , testcase); 49 50 int64_t endtime = getTime(); 51 int64_t cost = endtime - starttime ; 52 53 cout << "白名单大小：" << white.size() 54 << "测试数据大小：" << testcase.size() 55 << "未出现在白名单的数据的总和：" << cnt 56 << "花费时间：" << (cost/1000) << " ms" << endl ; 57 return 0; 58 } 59 60 void readfile(const string &filename , vector<int> &vec) 61 { 62 vec.clear(); 63 FILE* fp = fopen(filename.c_str() , "rb") ; 64 if(NULL == fopen) 65 { 66 fprintf(stderr ,"Usage :%s open failure", filename.c_str()); 67 exit(EXIT_FAILURE); 68 } 69 70 char buf[128]; 71 while(memset(buf ,0,sizeof buf),fgets(buf ,sizeof buf ,fp)!= NULL) 72 { 73 int val = atoi(buf); 74 vec.push_back(val); 75 } 76 fclose(fp); 77 } 78 79 bool BinarySearch(const vector<int> &vec , int val) 80 { 81 int low = 0 ; 82 int high = vec.size() - 1 ; 83 84 while(low <= high) 85 { 86 int mid = (low + high)/ 2 ; 87 if(val == vec[mid]) 88 return true ; 89 else if(val > vec[mid]) 90 low = mid + 1 ; 91 else 92 high = mid - 1 ; 93 } 94 return false ; 95 } 96 97 bool SimpleSearch(const vector<int> &vec , int val) 98 { 99 for(vector<int>::size_type ix = 0 ;ix != vec.size() ; ix++)100 {101 if(vec[ix] == val)102 return true ;103 }104 return false ;105 }106 107 int findandprint(const vector<int> &white , const vector<int> &data )108 {109 int cnt = 0 ;110 for(vector<int>::size_type ix = 0 ; ix != data.size() ; ++ ix)111 {112 if(!BinarySearch(white , data[ix]))113 {114 cout << data[ix] << endl ;115 cnt ++ ;116 }117 }118 return cnt ;119 }120 121 int64_t getTime()122 {123 struct timeval tm ;124 memset(&tm , 0 , sizeof(tm));125 if(gettimeofday(&tm ,NULL) == -1)126 {127 perror("gettimeofday");128 }129 130 int64_t t = 0 ;131 t += tm.tv_sec * 1000 * 1000;132 t += tm.tv_usec ;133 return t ;134 }
本文编译代码：
1 g++ BinarySearch.cc2 3 ./a.out white.txt testcase.txt
C++学习之二分查找续
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。