Friday, April 11, 2008

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;  }`