#include <stdio.h>
#define SIZE 9

/* Terry Harvey CISC105 Section 21 TA Aaron*/

/* Binary search with fewer comparisons */
int binSearch(int data[], int start, int end, int key);

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

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

/* How many comparisons are done in the first code we wrote, each time
   we call the function? How many comparisons are done here? How could
   we find out if the difference is significant? */
int binSearch(int data[], int start, int end, int key){

    int mid = (end + start)/2;

    if (start >= end){/*why test this, and then break it down?*/
        if (start > end)
            return -1; /* it isn't there*/
        else if (data[mid] == key)
            return mid;
        else return -1;
    }
    else {
        if (data[mid] < key){
            start = mid + 1; //this could go in the call too
            return binSearch(data, start, end, key); 
        }
        else {/* if (data[mid] >= key)*/
            end = mid; ///this could go in the call; it's here for clarity
            return binSearch(data, start, end, key); 
        }
    }
}