// invoke this as ./a.out 1000000 100
// ./a.out <array-size> <num-iterations>

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//#define N	1000000
typedef int (*searchFun)(int *, int, int);	// function pointer type

int *initArray(int n) {
	// create a random sorted array
	int curr = 0;
	int *arr = (int *)malloc(n * sizeof(int));
	for (int ii = 0; ii < n; ++ii) {
		curr = curr + rand() % 10;
		arr[ii] = curr;
	}
	return arr;
}
void printArray(int *arr, int n) {
	for (int ii = 0; ii < n; ++ii)
		printf("%d ", arr[ii]);
	puts("");
}
int linearSearch(int *arr, int n, int key) {
	for (int ii = 0; ii < n; ++ii)
		if (arr[ii] == key) return 1;
	return 0;
}
int binarySearch(int *arr, int n, int key) {
	int start = 0, end = n - 1;

	while (start <= end) {
		int mid = (start + end) / 2;
		if (key == arr[mid]) return 1;
		else if (key < arr[mid])
			end = mid - 1;
		else
			start = mid + 1;
	}
	return 0;
}
void profileSearch(int numiter, int *arr, int n, searchFun fun, char *display) {
	clock_t starttime, endtime;

	starttime = clock();
	for (int ii = 0; ii < numiter; ++ii) {
		int key = rand() % (10 * n);
		(*fun)(arr, n, key);	// ignoring the return value
	}
	endtime = clock();
	printf("Time taken by %s = %lf seconds\n", display, ((double) (endtime - starttime)) / CLOCKS_PER_SEC);
}
int main(int a, char *b[]) {
	if (a < 3) {
		printf("Usage: %s <array-size> <number-of-iterations>\n", *b);
		exit(1);
	}
	int N = atoi(b[1]);
	int *arr = initArray(N);
	//printArray(arr, N);

	int numiter = atoi(b[2]);
	profileSearch(numiter, arr, N, linearSearch, "Linear Search");
	profileSearch(numiter, arr, N, binarySearch, "Binary Search");

	// Additional time functions: time(), difftime(), localtime(), strftime().
	return 0;
}