Search in a Sorted List

Implement a function which, given an array of sorted numbers and a number will determine if that number is in the array.


The solution is to implement a binary search algorithm. As Programming Pearls tells us, this is a notoriously difficult simple algorithm to get correct. Much unit testing is needed. In fact, the one I wrote below is probably wrong.

There are two implementations: one is recursive and I am fairly sure that one is correct, and the other is iterative and I can't be sure its really completely correct without a lot of testing.

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

using namespace std;

bool myBinarySearchHelper(vector<int> & v, int start, int end, int e){
  if (start == end) 
    return (e == v[start]);
  int mid = (end+start)/2;
  if (e <= v[mid])
    return myBinarySearchHelper(v,start,mid,e);
  else 
    return myBinarySearchHelper(v,mid+1,end,e);
}

bool myBinarySearchRecursive(vector<int> & v, int e){
  return myBinarySearchHelper(v, 0 , v.size(), e);
}

bool myBinarySearch(vector<int> & v, int e){
  int start = 0;
  int end = v.size();
  while (start < end){
    int mid = (end+start)/2;
    if (e == v[mid])
      return true;
    if (e < v[mid])
      end = mid;
    else
      start = mid + 1;
  }
  return false;
}

void print(int e){
  cout << e << ' ';
}

int main() {
  vector<int> v;
  v.push_back(1); v.push_back(2); v.push_back(3); 
  v.push_back(4); v.push_back(6); v.push_back(8);
  v.push_back(9); v.push_back(10);
  
  for_each(v.begin(), v.end(), print);
  cout << endl;
  
  for (int i = 3; i< 12; i++){
    if (myBinarySearch(v, i)) 
      cout << i << " is in " << endl;
    else
      cout << i << " is not in" << endl;
  }
  return 0;
  
}