#include <iostream>

using namespace std;

void PrintArray(int a[], size_t size);
bool BinarySearch(int a[], int begin, int end, int key);

int main() {
    int a[] {1, 5, 9, 12, 15, 19};

    PrintArray(a,6);

    for(int i=0; i < 23; i++) {
       PrintArray(a,6);
       cout << "Searching for "  << i << endl;
       if(BinarySearch(a,0,5,i) ) {
           cout << "FOUND." << endl ;
       } else {
           cout << "not found " << endl ;
       }
       cout << endl;
    }

    return 0;
}

bool BinarySearch(int a[], int begin, int end, int key) {
   int mid;

   cout << "\tSearching for " << key << " begin = " << begin << " end = " 
        << end << endl;
   if (begin > end) {
       cout <<"\t\t out of range, begin > end" << endl;
       return false;
   } 

   mid = (begin+end)/2;
   cout << "\t\t mid = " << mid << endl;

   if (a[mid] == key) {
       cout << "\t\t key=a[mid], found" << endl;

       return true;
   } else if (a[mid] > key) {
       cout << "\t\t key > a[mid], recursively searching low" << endl;
       return BinarySearch(a,begin, mid-1, key);
   } else {
       cout << "\t\t key < a[mid] recursively searching high" << endl;
       return BinarySearch(a, mid+1, end, key);
   }

}

void PrintArray(int a[], size_t size) {
    size_t i;

    cout << a[0];
    for(i = 1; i < size; i++) {
       cout << " " << a[i];
    }
    cout << endl;
    return;
}