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

#define N (1024*1024)

void init(int *a) {
	srand(time(NULL));
	//srand(0);
	for (int ii = 0; ii < N; ++ii)
		a[ii] = rand() % 100;
}
void print(int *a) {
	for (int ii = 0; ii < 10; ++ii)	// printing first 10.
		printf("%d ", a[ii]);
	printf("...\n");
}
int searchnby2(int *a, int x, int start, int end) {
	//printf("s = %d, e = %d\n", start, end);
	if (start >= end) return 0;
	if (a[start] == x) return 1;
	int first = searchnby2(a, x, start + 1, (start + end) / 2 + 1);
	if (first) return 1;
	int second = searchnby2(a, x, (start + end) / 2 + 1, end);
	return second;
}
int searchnminus1(int *a, int x, int start, int end) {
	if (start >= end) return 0;
	if (a[start] == x) return 1;
	return searchnminus1(a, x, start + 1, end);
}
int main() {
	int a[N];
	init(a);
	print(a);
	int x = -1;
	//int x = rand() % 100;

	int found = searchnby2(a, x, 0, N);
	if (found) printf("found %d\n", x);
	else printf("not found %d\n", x);

	int found2 = searchnminus1(a, x, 0, N);
	if (found2) printf("found %d\n", x);
	else printf("not found %d\n", x);
}