/*
 * Created on Aug 3, 2005
 * 
 * CPS 006 - Summer 05
 * Sam Slee
 * BinarySearch.java
 * 
 * 
 */

import cs1.Keyboard;

public class BinarySearch {
	
	//--------------------------------------------------------------------------------
	// Starter method for exercising the binary search recursive method
	public static void main(String[] args) {
		int[] input = {2, 4, 5, 12, 19, 23, 36, 44, 77, 81, 81, 101, 156};
		int goal = 0;
		
		System.out.println("Array entries: ");
		for(int i=0; i<input.length; i++)
			System.out.print(input[i]+" ");
		
		System.out.print("\n\nEnter a number to search for: ");
		goal = Keyboard.readInt();
		
		boolean inArray = binarySearch(input, 0, input.length, goal);
		
		System.out.println("\nWas the entry found: "+inArray);
	}

	
	//--------------------------------------------------------------------------------
	// recursively uses binary search to find the "goal" entry in the "input" array
	// NOTE: Assumes that the input array is in sorted order.
	public static boolean binarySearch(int[] input, int startIndex, int endIndex, int goal){
		
		System.out.println("Searching in the range: "+startIndex+" "+endIndex);
		
		if(startIndex > endIndex)
			return false;
		
		int middle = (endIndex + startIndex)/2;
		System.out.println(input[middle]);
		
		if(input[middle] == goal)
			return true;
		else if(input[middle] < goal)
			return binarySearch(input, middle+1, endIndex, goal);
		else
			return binarySearch(input, startIndex, middle-1, goal);
	}
}