/*!\file:  binary_search.cpp
 * \brief  binary search on an integer array, that is already sorted
 */ 

#ifdef HAVE_CONFIG_H
	#include "config.h"
#else
#error "Cannot compile with HAVE_CONFIG_H symbol! run configure first!"
#endif

#undef __FUNCT__ 
#define __FUNCT__ "binary_search"

#include "stdio.h"

int binary_search(int* poffset,int target, int* sorted_integers,int num_integers){

	/*output: */
	int offset;  //offset, if found
	int found=0;  //found=0 if target is not found, 1 otherwise.

	/*intermediary: */
	int* beg=NULL;
	int* end=NULL;
	int* mid=NULL;

	// point to beginning and end of the array
	beg=sorted_integers;
	end=sorted_integers+num_integers;
	mid=beg+(int)(num_integers/2);

	if (*beg==target){
		found=1;
		offset=0;
	}
	else if(*(end-1)==target){
		found=1;
		offset=num_integers-1;
	}
	else{
		while((beg <= end) && (*mid != target)){
			#ifdef _DEBUG_
				printf("1: %i %i %i\n",*beg,*mid,*(end-1));
			#endif
			// is the target in lower or upper half?
			if (target < *mid) {
				end = mid - 1;  //new end
				mid = beg + (end-beg)/2;  //new middle
			}
			else {
				beg = mid + 1;  //new beginning
				mid = beg + (end-beg)/2;  //new middle
			}
			#ifdef _DEBUG_
				printf("2: %i %i %i\n",*beg,*mid,*(end-1));
			#endif
		}
			  
		//did we find the target?
		if (*mid == target) {
			found=1;
			offset=mid-sorted_integers;
		}
		else {
			found=0;
		}
	}

	/*Assign output pointers:*/
	*poffset=offset;
	
	/*Return result: */
	return found;
}

