Binary search saying 0 Numbers are found?

Question

I am working on a project where I use a Binary search to look through a vector. When I output the data linear search completes properly but Binary search does not.

The output: ------ Data source: 132 unique random numbers ------ 80 81 67 20 187 90 53 13 103 100 83 11 198 124 171 52 68 2 130 172 50 65 102 38 117 196 127 140 22 42 99 120 9 158 115 192 169 43 186 69 176 55 182 15 143 37 23 151 41 164 48 77 183 1 54 79 5 199 93 141 33 150 162 56 110 24 6 173 44 154 78 85 112 200 144 166 72 195 126 35 64 193 177 47 131 94 88 137 96 95 160 122 111 165 108 49 184 4 116 66 138 8 142 16 63 148 57 70 170 21 59 159 139 75 58 174 180 25 152 132 121 194 82 190 71 181 97 10 106 39 178 46 ------ 100 random numbers to be searched: ------ 66 158 40 148 80 160 146 112 154 128 2 166 180 177 183 179 9 78 83 24 107 162 54 149 84 134 9 151 200 179 197 18 137 37 117 168 196 62 79 102 142 32 67 121 8 1 51 168 78 85 191 136 46 196 85 81 130 45 31 81 23 180 98 159 16 166 126 163 28 156 64 121 187 82 41 147 83 44 114 112 128 105 48 126 52 84 158 181 128 141 62 102 120 111 61 87 77 138 49 56

Linear search: 100 numbers are found. The average number of comparisons in each search: 52

Binary search: 0 numbers are found. The average number of comparisons in each search: 7

------- numbers in data source are now sorted ---------

Linear search: 100 numbers are found. The average number of comparisons in each search: 47.41

Binary search: 0 numbers are found. The average number of comparisons in each search: 7

  #include <algorithm>
  #include <iostream>
  #include <iomanip>
  #include <vector>

  const int DATA_SIZE = 200;
  const int DATA_RANGE = 200;
  const int DATA_SEED = 9;
  const int SEARCH_SEED = 17;

  using namespace std;


  int linear_search(const vector<int>& inputVec, const int x, int& 
  comparisons) {
  comparisons = 0;

  for (size_t i = 0; i < inputVec.size();i++)
  {
    comparisons++;
    if (x == inputVec[i])
        return i;
    if (x >= inputVec.size())
        return 0;
   }
   }

   int binary_search(const vector<int>& inputVec, const int x, 
   int& comparisons) {
   int mid = 0;
   int beg = 0;
   int end = inputVec.size();
   comparisons = 0;

   for (size_t x = 0; beg <= end; x++) {
    mid = (end + beg) / 2;
    comparisons++;
    if (x == inputVec[mid]) {
        return x;
    }
    else if (x < inputVec[mid])
        end = mid-1;
    else
        beg = mid+1;
   }
    return -1;
 }

  void print_vec(const vector<int>& vec) {
  vector<int>::const_iterator begin = vec.begin();
  int line = 0;
  cout << setw(6);
  for (size_t i = 0; i < vec.size(); begin++,i++)
  {
    if ((*begin / 5) < 1)
        cout << *begin << setw(6);
    else if ((*begin / 10) == 5)
        cout << *begin << setw(6);
    else 
        cout << *begin << setw(6);
    line++;
    if (line == 5){
        line = 0;
        cout << endl;
        cout << setw(6);
    }

   }
 }

 void average_comparisons(const vector<int>& inputVec, const 
 vector<int>& searchVec, int(*search)(const vector<int>&, const 
 int, int&)) {
 int i, comparison = 0, sum = 0, found = 0;
 int res = 0;
 for (i = 0; i < (int)searchVec.size(); i++) {
    res = search(inputVec, searchVec[i], comparison);
    sum += comparison;
    if (res >= 0)
        found++;
   }
  cout << found << " numbers are found. The average number of 
  comparisons in each search: " << (double)sum / 
  (double)searchVec.size() << endl << endl;
  } 

  int random_number() {
  return rand() % DATA_RANGE + 1;
 } 


int main() {

// -------- create unique random numbers ------------------//
vector<int> inputVec(DATA_SIZE);
srand(DATA_SEED);
generate(inputVec.begin(), inputVec.end(), random_number);
sort(inputVec.begin(), inputVec.end());
vector<int>::iterator it = unique(inputVec.begin(), 
inputVec.end());
inputVec.resize(it - inputVec.begin());
random_shuffle(inputVec.begin(), inputVec.end());

cout << "------ Data source: " << inputVec.size() << " unique 
random numbers ------" << endl;
print_vec(inputVec);
cout << endl;

// -------- create random numbers to be searched ---------//
vector<int> searchVec(DATA_SIZE / 2);
srand(SEARCH_SEED);
generate(searchVec.begin(), searchVec.end(), random_number);

cout << "------ " << searchVec.size() << " random numbers to be 
searched: ------" << endl;
print_vec(searchVec);
cout << endl;

cout << "Linear search: ";
average_comparisons(inputVec, searchVec, linear_search);
cout << "Binary search: ";
average_comparisons(inputVec, searchVec, binary_search);

sort(inputVec.begin(), inputVec.end());
cout << "------- numbers in data source are now sorted ---------" 
<< endl << endl;
cout << "Linear search: ";
average_comparisons(inputVec, searchVec, linear_search);
cout << "Binary search: ";
average_comparisons(inputVec, searchVec, binary_search);

return 0;

} 

Answer 1

As others have already pointed out both linear_search and binary_search are flawed in your code. I recommend you to take a look at a proper binary search implementation. It is in Java, but understanding it shouldn't be a problem. Other than that, your array must be sorted in ascending order, otherwise binary search won't work.

If you are interested in further details about the algorithm, I highly encourage you to search for the authors of the source code linked above.