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

#define TEST_COUNT 1000


typedef int bool;
typedef int (*searcher)(int *A, int x, int l, int r);

int cmp(const void *a, const void *b) { return *(int*)b - *(int*)a; }

int linsearch(int *A, int x, int n) {
	int i;
	for (i = 0; i < n; i++) {
		if (A[i] == x) {
			return i;
		}
	}
	return -1;
}

void print(int *A, int n) {
	printf("[");
	if (n > 0) {
		printf("%d", A[0]);
	}
	int i;
	for (i = 1; i < n; i++) {
		printf(", %d", A[i]);
	}
	printf("]\n");
}

void test(searcher s) {
	//~ if (s(0, 0, 0, -1) != -1) {
		//~ printf("FAIL! []\n");
		//~ return;
	//~ }
	
	int A[TEST_COUNT];
	int i, j;
	for (i = 1; i < TEST_COUNT; i++) {
		for (j = 0; j < i; j++) {
			A[j] = abs(rand()) % i;
		}
		int x = abs(rand()) % i;
		
		qsort(A, sizeof(int), i, cmp);
		
		int k = s(A, x, 0, i-1);
		int l = linsearch(A,x,i);
		if (k == -1) {
			if (l != -1) {
				printf("FAIL! x = %d, k = %d, l = %d\n", x, k, l);
				print(A, i);
				return;
			}
		} else if (A[k] != x) {
			printf("FAIL! x = %d, k = %d, l = %d\n", x, k, l);
			print(A, i);
			return;
		}
	}
	printf("OK!\n");
}

int mock(int *A, int x, int l, int r) {
	return linsearch(A, x, r);
}


int szuk_rek(int *A, int X, int L, int R){
//        printf("L =%d R = %d\n", L, R);
        if(A[L] > X || A[R] < X){
                return 0;
        }
        if(A[R]==X){
                return R;
        }
        if(L > R){
                return -1;
        }
        if( L == R && A[L] != X){
                return -1;
        }
 
        if (A[(L+R)/2]== X){
                return (L+R)/2;
        }
 
        if( A[(L+R)/2] < X){
                return szuk_rek(A, X, (L + R)/2, R);
        }
        if( A[(L+R)/2] > X){
                return szuk_rek(A, X, L, (L + R)/2);
        }
        
}

int main(void) {
	srand(6);
	
	test(szuk_rek);
	
	
	
	return 0;
}