首页 > 代码库 > C++学习之二分查找
C++学习之二分查找
//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;
//写入文件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");}//返回timedouble 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"); for(int i = 0; i != kSize; ++i) { writeIntegerToFile(fd, rand() % kSize); } close(fd); 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;}
C++学习之二分查找
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。