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.


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);
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;
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;
cout << i << " is not in" << endl;
return 0;


No comments: