import java.util.Arrays;


public class BinarySearch {

	/*
	 * Precondition: a is sorted
	 * Postcondition: Returns the index of an occurrence of the given
	 * value in the given array, or -1 if not found.
	 */
	public int binarySearch(int[] a, int target) {
	    return binarySearch(a, target, 0, a.length - 1);
	}

	/*
	 * Precondition: a is sorted; 0<=first<=a.length-1; 0<=last<=a.length-1; first<=last
	 * Postcondition: Returns the index of an occurrence of the given
	 * value in the given array, or -1 if not found.
	 */	
	private  int binarySearch(int[] a, int target, int first, int last) {
		if (first > last) {
			return -1;   // not found
		} 
		int mid = (first + last) / 2;
		if (a[mid] == target) {
			return mid;   // found it!
		} 
		else{
			if (a[mid] < target) {
				// middle element too small; search right half
				return binarySearch(a, target, mid+1, last);
			}
			else {  // a[mid] < target
				// middle element too large; search left half
				return binarySearch(a, target, first, mid-1);
			}
		}
	}

	
	public static void main(String[] args) {

		BinarySearch search = new BinarySearch();
		int [] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

		int index;
		index = search.binarySearch(a, -1);
		System.out.println("index: " + index);
		index = search.binarySearch(a, 6);
		System.out.println("index: " + index);
	}

}