C++学习之二分查找续

  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.cc
2 
3 ./a.out white.txt testcase.txt