/***********************************************************************************************
 *
 * HOWTO RUN: 
   gcc -std=gnu99 -Wall -gstabs+ binsrch.c && valgrind -v --leak-check=full ./a.out 2> /tmp/2
 *
 ***********************************************************************************************/

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

const int TEST_ITERATIONS = 10000;

int my_ctr = 0;
int sample_ctr = 0;
int matches = 0;
int no_matches = 0;

/**
 * 
 * Recursive binary search
 *
 * @param a:      haystack int array
 * @param item:   needle, the item to find from the array
 * @param bottom: current lowest index of the array we're searching
 * @param top:    current highest index of the array we're searching, starting w/size-1
 *
 * @return -1,  if item is not in the array, 
 * @return idx, otherwise the index of the haystack int array that holds the sought value
 * 
 */
int binsrch(int *a, int item, int bottom, int top)
{
	my_ctr++;	

	int i=(bottom+top)/2;

	if(a[i]==item) {
		return i;
	}

	if(bottom>=top) {
		return -1;
	}

	if(item<a[i]) {
		return binsrch(a,item,bottom,i-1);
	}

	return binsrch(a,item, i+1, top);
}

/**
 *
 * I grabbed this from http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/
 * because I wanted a reference function for performance testing. The current performance
 * is identical, steps-wise. Both functions use the same amount of attempts before they
 * find the match or figure out that there isn't one.
 *
 */
int binary_search(const int a[], const int size, const int val) {
    int lower = 0;
    int upper = size-1;

    /* invariant: if a[i]==val for any i, then lower <= i <= upper */
    /* bound function: upper-lower+1 */
    while (lower <= upper) {
	++sample_ctr;
        int i = lower + (upper-lower)/2;
        if (val == a[i]) {
            return i;
        } else if (val < a[i]) {
            upper = i-1;
        } else { /* val > a[i] */
            lower = i+1;
        }
    }
    return -1;
}


void test()
{
	int sz = random() % 200; // how large haystack
	
	if(sz<20) {
		sz=20;
	}

	int buf[sz];

	//for(int i=0,j=0; i<sz; i++,j++) {
	for(int i=-10,j=0; i<sz-10; i++,j++) {
		buf[j] = i;
	}

	int search = random() % (sz*30); // how many needles in haystack
	int match = binary_search(buf, sz, search);   
	int my_match = binsrch(buf, search, 0, sz-1);

	fprintf(stderr, "my=(%d) sample=(%d) sz=%d, search=%d, match=%d, my_match=%d\n",
			my_ctr, sample_ctr, sz, search, match, my_match);

	if(match!=my_match) {

		printf("P A N I C\n");
		exit(1);
	}

	if(match==-1) 
		no_matches++;
	else
		matches++;

	fprintf(stderr, "-----------------------------------------------------------\n");

}

int main(int argc, char** argv)
{
	int my, sample;
	my = sample = 0;
	for(int i=0; i<TEST_ITERATIONS; i++) {
		srandom(getpid() + my);
		test();
		my += my_ctr;
		sample += sample_ctr;
		my_ctr = sample_ctr = 0;
	}
	

	printf("TOT: test_iters=%d, my=%d, sample=%d, diff=%d\n", TEST_ITERATIONS, my, sample, sample-my);
	printf("matches=%d, no_matches=%d, %d%% of tests were matches.\n", matches, no_matches, (100*matches)/(matches+no_matches));

	return 0;
}