public class BinarySearch			// recursive implementation of binary search
{
	public static void main(String[] args)
	{
		int[] nums={1, 3, 4, 6, 7, 10, 14, 15, 21, 22, 80, 99};		// assume array is sorted
		int low=0,high=nums.length-1;								// initialize area of search (0 to length-1)
		int target=6;												// we will look for the index storing the value target
		System.out.println(find(nums,low,high,target));
	}
	
	public static int find(int[] array, int l, int h, int t)		// l is low index, h is high index, t is the target value
	{
		if(l>h) return -1;											// if low > high, we have not found target, return -1 to indicate target not in array
		else {
			int mid=(l+h)/2;										// otherwise reset mid point to be halfway between low and high
			if(array[mid]==t) return mid;							// if we find t at midpoint, return midpoint
			else if(array[mid]>t) return find(array,l,mid-1,t);		// if the value at midpoint > target, we are searching too high, lower high to be midpoint-1
			else return find(array,mid+1,h,t);						// otherwise we are searching too low, raise low point to be midpoint+1
		}		
	}
	
	// example:
	// [1, 3, 4, 6, 7, 10, 14, 15, 21, 22, 80, 99] target=6, low=0, high=11
	// low<=high, continue, mid=(0+11)/2=5
	// array[5]=10, too high, reset high to mid-1 (4)
	// [1, 3, 4, 6, 7] target=6, low=0, high=4
	// low<=high, continue, mid=(0+4)/2=2
	// array[2]=4, too low, reset low to mid+1 (3)
	// [6, 7], target=6, low=3, high=4
	// low<=high, continue, mid=(3+4)/2=3
	// array[3]=6, return mid
	
	// run the program with target=81 and you will receive -1
}