C++学习之路：循环实现二分查找

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int BinSearch(vector<int> ivec, int key)   //循环实现的二分查找要比递归实现效率要高很多，推荐使用这种方法
{
    int low = 0, high = ivec.size() -1, mid;  //注意high的边界值，ivec.size()指向的是最后一个元素的下一个元素（即指向越界的内存）;
    if(ivec[low] == key)
        return low;
    if(ivec[high] == key)
        return high;
    mid = low + (high - low) / 2;

    if(ivec[mid] == key)
        return mid;
    if(ivec[mid] > key)
        high = mid - 1;
    if(ivec[mid] < key)
        low = mid + 1;

    if(low > high)
        return -1 //没有找到则返回 -1；
}


int main(int argc, const char *argv[])
{
    
    return 0;
}

以下是实现的代码

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <iostream>
 5 #include <string>
 6 #include <vector>
 7 #include <fcntl.h>
 8 #include <unistd.h>
 9 #include <sys/time.h>
10 #include <algorithm>
11 #define ERR_EXIT(m) 
12     do { 
13         perror(m);
14         exit(EXIT_FAILURE);
15     }while(0)
16 using namespace std;
17 
18 const int size = 1000000;
19 
20 int binarySearch(vector<int> vec, int key)
21 {
22     int low = 0, high = vec.size() - 1, mid;
23     while(low <= high)
24     {
25         if(vec[low] == key)
26             return low;
27         if(vec[high] == key)
28             return high;
29         mid = low + ((high - low) / 2);
30         if(vec[mid] == key)
31             return mid;
32         else if(vec[mid] > key)
33             high = mid - 1;
34         else
35             low = mid + 1;
36     }
37     if(low > high)
38         return -1;
39 }
40 
41 int binarySearch2(vector<int> vec, int low, int high, int key)
42 {
43     int mid = low + (high - low) / 2;
44     if(low > high)
45         return -1;
46     else
47     {
48         if(vec[mid] == key)
49             return mid;
50         else if(vec[mid] > key)
51             return binarySearch2(vec, low, mid - 1, key);
52         else 
53             return binarySearch2(vec, mid + 1, high, key);
54     }
55 }
56 int main(int argc, const char *argv[])
57 {
58     time_t starttime = time(NULL);
59     FILE *fp1 = fopen("largeW.txt", "rb");
60     FILE *fp2 = fopen("largeT.txt", "rb");
61     if(fp1 == NULL || fp2 == NULL)
62     {
63         ERR_EXIT("fopen"); 
64     }
65 
66     vector<int> ivec;
67     int val, cnt = 0;
68     while(fscanf(fp1, "%d", &val) == 1)
69     {
70         ivec.push_back(val);
71     }
72     sort(ivec.begin(), ivec.end());
73   
74     while(fscanf(fp2, "%d", &val) == 1)
75     {
76         //if(binarySearch2(ivec, 0, ivec.size() - 1, val) >= 0)
77         if(binarySearch(ivec, val) >= 0)
78             continue;
79         else
80         {
81             cout << val << " ";
82             cnt++;
83         }
84     }
85     cout << endl << cnt << endl;
86     
87     fclose(fp1);
88     fclose(fp2);
89     time_t endtime = time(NULL);
90     time_t cost = endtime - starttime;
91     cout << "time cost : " << cost << "s" << endl;
92     return 0;
93 }

C++学习之路： 循环实现二分查找

C++学习之路：循环实现二分查找