/* 	Example 9.5: Binary search
	Source: Gilberg and Forouzan, p. 41-42
	Modification: Peter Brusilovsky
	
	Reads array from st input, then requests element
	to be found until it can be found.
*/

#include <stdio.h>
#define N 7 /* dimension of the array */
int readarray(int ar[], int n);
int binarySearch(int list[], int last, int target);

main() {

	/* declare an array */
	int testarray[N];
	int mytarget, index;
	
	/* read data */
	readarray(testarray, N);
	do {
		/* get target */
		printf("Enter target: ");
		scanf("%d", &mytarget);
		
		/* find */
		if ((index = binarySearch(testarray, N, mytarget)) == -1 ) 
			printf("Target %d not found\n", mytarget);
		else 
			printf("Target %d is located at index %d\n", mytarget, index);
	} while(index == -1); /* loop ends when the requested element found */
	return 0;
}

/* array input */
int readarray(int ar[], int n_of_elements) {
	int i;
	for (i = 0; i < n_of_elements; ++i) {
		printf("%d> ", i);
		scanf("%d", &ar[i]);
	}
	return 0;
}


int binarySearch   (int list[ ], int end, int target ) {
	int first, mid, last;

	first = 0 ;
	last = end - 1;
	while ( first <= last ) {
		 mid = ( first + last ) / 2 ;
		 if ( target > list[ mid ] )
			/* look in upper half */
			first = mid + 1 ;
		 else if ( target < list[ mid ] )
				/* look in lower half */
				last = mid - 1 ;
		 else
				/* found equal: force exit */
				return mid ;
		}	/* end while */
	return -1;
}