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;

}

## No comments:

Post a Comment