/* Exerecise 3.1 from "The C programming language" book by K&R */

#include <stdio.h>
#include <time.h>
#define N 10000		/* size of massive */

/* search x in v[0] <= v[1] <= ... <= v[n-1]. function from book */
int binsearch(int x, int v[], int n)
{
	int low, high, mid;
	low = 0;
	high = n - 1;
	while (low <= high) {
		mid = (low+high) / 2;
		if (x < v[mid])
			high = mid - 1;
		else if (x > v[mid])
			low = mid + 1;
		else
			return mid;
	}
	return -1;
}

/* search x in v[0] <= v[1] <= ... <= v[n-1]. function by me */
int binsearch2(int x, int v[], int n)
{
	int low, high, mid;
	low = 0;
	high = n - 1;
	mid = (low+high) / 2;
	while (low <= high && x != v[mid]) {
		if (x < v[mid])
			high = mid - 1;
		else
			low = mid + 1;
		mid = (low+high) / 2;
	}
	if (x == v[mid])
		return mid;
	else
		return -1;	
}

int main(void)
{
	int mas[N];
	int i;
	clock_t clock1;
	clock_t clock2;

	for (i = 0; i < N; i++)		/* fill in initial massive */
		mas[i] = i;

	clock1 = clock();
	binsearch(1, mas, N);
	clock2 = clock();
	printf("binsearch() time = %lu\n", (unsigned long int)(clock2-clock1));

	clock1 = clock();
	binsearch2(1, mas, N);
	clock2 = clock();
	printf("binsearch2() time = %lu\n", (unsigned long int)(clock2-clock1));
	return 0;
}