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

using namespace std;

const int NOT_FOUND = -1;

template <typename T> 
int BinarySearch(const vector<T> &  data, T key, int start=0, int end=-99) {
    int mid;

    if (end == -99) {
       end = static_cast<int>(data.size())-1;
    }

    if ( end < start) {
        return NOT_FOUND;
    }

    mid = (start+end)/2;
    if (data[mid] == key) {
        return mid;
    } else if (data[mid] < key) {
        return BinarySearch(data, key, mid+1, end);
    } else {
        return BinarySearch(data, key, start, mid-1);
    }

}


int main() {
    vector<int> myData;
    int i;
    int current = 0;
    int pos;


    for(i =0; i < 10; i ++) {
       
       myData.push_back(current);
       current += rand() % 4 + 1;
    }

    cout << "The data is " << endl;
    for (auto x: myData) {
       cout << x << " " ;
    }
    cout << endl << endl;

    for(i =-1; i < myData.back()+4; i++) {
        cout << "Searching for " << i ;
        pos = BinarySearch(myData, i);
        if (pos == NOT_FOUND) {
            cout << " nope!" << endl;
            if (find(begin(myData), end(myData) , i) != end(myData)) {
               cout << "Error, " << i 
                    << " not found but should have been" <<endl;
            }
        } else {
            cout << " yep!" << endl;
            if (i != myData[pos]){
                cout << "Error, " << i << " found at " 
                     << pos << " but " << myData[pos] << " is there" << endl;
            }
        }
    }

    return 0;

}