#include <iostream>
#define SIZE 100
#define DEBUG 1;
using namespace std;

/*
 * Why is binary search such a widely used tool? Under what
 * circumstances is it applicable? Can you trace the code behavior for
 * various inputs? If you "break" this program, can you predict how it
 * will behave?
 */

int binSearch(int data[], int key, int start, int end);

int main(){

    int a[SIZE];

    for (int i = 0; i < SIZE; i++)
	a[i] = i;

    cout << binSearch(a, 6, 0, SIZE - 1 ) << endl;

    return 0;
}

int binSearch(int data[], int key, int start, int end){

    int mid = start + (end - start) / 2;
    if (DEBUG) cout << key << " " <<" start "<< start << " end " 
	 << end << " mid " << mid << endl;
    if (start > end){
	return -1;
    }
    else if (key < data[mid]){
	return binSearch( data,  key, start, mid - 1);
    }
    else if (key > data[mid]){
	return binSearch( data,  key, mid + 1, end);
    }
    else { //key is == mid
	return mid;
    }
}