#include <stdio.h>
#define SIZE 1000000
/**
 * Terry Harvey CIS 105 Section 010 TA Tina Weymouth
 *  Demonstration program for binary search.
 **/
void printArray(int data[], int size);

int main(){

    int data[SIZE];
    int key;
    int i;

    do {

        printf("Enter a key to search for: ");
        scanf("%d", &key);

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

        //    printArray(data, SIZE);
        printf("found %d at %d\n", key, binSearch(data, 0, SIZE - 1, key));

    } while (key != -1);
 
    return 0;

}
/* Returns the index of key in data OR return -1 if key is not
 * found. 
 */
int binSearch(int data[], int start, int end, int key){
    int mid;
    printf("inside binSearch start %d, end %d\n", start, end);

    if (start > end) return -1;

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


void printArray(int data[], int size){
    int i;
    for ( i = 0; i < size; i++)
        printf("%d ", data[i]);
    printf("\n");
    return;
}