#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) {
    int i = *(int*)a;
	int j = *(int*)b;
	return (i < j) ? -1 : (i == j) ? 0 : 1;
}

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, 0) != -1) {
		printf("FAIL! []\n");
		return;
	}
	
	int A[TEST_COUNT];
	int i, j;
	for (i = 1; i < TEST_COUNT; i++) {
		printf("(%d tests)...\r", i);
		fflush(stdout);
		for (j = 0; j < i; j++) {
			A[j] = abs(rand()) % i;
		}
		int x = abs(rand()) % i;
		
		qsort(A, i, sizeof(int), cmp);
		
		int k = s(A, x, 0, i);
		int l = linsearch(A,x,i);
		if (k == -1) {
			if (l != -1) {
				printf("\nFAIL! x = %d, k = %d, l = %d\n", x, k, l);
				print(A, i);
				return;
			}
		} else if (A[k] != x) {
			printf("\nFAIL! x = %d, k = %d, l = %d\n", x, k, l);
			print(A, i);
			return;
		}
	}
	printf("OK!                   \n");
}


int binSearch(int *xs, int x, int l, int r) {	
	if (l == r) { return -1; }	
	int m = (l+r-1)/2;
	return (xs[m] < x) ? binSearch(xs, x, m+1, r)
	     : (xs[m] > x) ? binSearch(xs, x, l, m)
	     :               m;
}

int szuk_rek(int *A, int X, int L, int R){
	if (R < 0) return -1;
	
//        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);
        }
       return -1;
}

int asdf(int *A, int X, int L, int R) {
	return szuk_rek(A,X,L,R-1);
}

int main(void) {
	srand(7);
	
	test(binSearch);
	test(asdf);
	
	return 0;
}