/* Modified binary search program (based on the one in _The C Programming 
Language_, p. 58) to make one search inside the loop instead of two. 
find x in v[0] <= v[1] <= ... <= v[n-1] */

#include <stdio.h>
#include <values.h>


int binsearch(int x, int v[], int n)
{
	int low, high, mid;
	low = 0;
	high = n-1;
	while (low < high - 1)  
	{
		mid = (low + high)/2;
		if (x <= v[mid])
			high = mid;
		else
			low = mid + 1;
	}
	if (v[low] == x)
		return low;
	else if (v[high] == x)
		return high;
	else
		return -1;
}

int main() {
	int test[99999];
	int result;
	int i;
	time_t now;

	/* initialize array */
	for(i = 0; i < 99999 ; i++)
		test[i] = i;

	now = time(NULL);
	/* try the search */
	result = binsearch(1, test, 99999);


	if(result == -1) {
		printf("%d not found!\n", 1);
	} else {
		printf("found %d at element %d.\n", 1, result);
	}
}