#include <stdio.h>
#define SIZE 9

/* Terry Harvey CISC105 Section 21 TA Aaron*/

/* Sample program for class */
int binSearch(int data[], int start, int mid, int end, int key);

int main(){
    int data[SIZE] = {1,5,8,9,41,55,76,81,300};

    int found = binSearch(data, 0, SIZE/2, SIZE - 1, 50);
    printf("found at %d\n", found);
    found = binSearch(data, 0, SIZE/2, SIZE - 1, 1);
    printf("found at %d\n", found);
    found = binSearch(data, 0, SIZE/2, SIZE - 1, 300);
    printf("found at %d\n", found);
    found = binSearch(data, 0, SIZE/2, SIZE - 1, 0);
    printf("found at %d\n", found);
    found = binSearch(data, 0, SIZE/2, SIZE - 1, 41);
    printf("found at %d\n", found);
    found = binSearch(data, 0, SIZE/2, SIZE - 1, 301);
    printf("found at %d\n", found);
    found = binSearch(data, 0, SIZE/2, SIZE - 1, 9);
    printf("found at %d\n", found);
    return 0;
}

int binSearch(int data[], int start, int mid, int end, int key){
    if (start > end)
        return -1; /* it isn't there*/

    else if (data[mid] < key){
        start = mid + 1;
        mid = (end + start)/2; //NOTE: Order is important 
        return binSearch(data, start, mid, end, key); 
    }
    else if (data[mid] > key){
        end = mid - 1;
        mid = (end + start)/2; //NOTE: Order is important 
        return binSearch(data, start, mid, end, key); 
    }
    else /* equals means key is found at mid */
        return mid;

}