import java.io.*;

public class BinarySearch
{
	public static int binSearch(int[] list, int key, int begin, int end)
	{
	
		System.out.print("called ");
		
		if (begin > end) return -1;
		
		int mid = (end + begin)/2;
		
		if (list[mid] == key) 
			return mid;
		else if (list[mid] > key)
			return binSearch(list, key, begin, mid-1);
		else
			return binSearch(list, key, mid+1, end); 
	}


static BufferedReader keyboard = new BufferedReader 
										    	(new InputStreamReader (System.in));


	private static int LISTLENGTH = 10;
	
	public static void main(String[] args) throws IOException
	{
		int[] list = new int[LISTLENGTH];
		int ind;
		
		for (int i = 0; i < list.length; i ++)
			list[i] = (int)(10*LISTLENGTH*Math.random());
			
		//make a key I'm sure is in the array.
		//int key = list[LISTLENGTH/2];
		
		SortingCode.selectionSort(list);
				
		SortingCode.print(list);
		
		System.out.println("Enter a key to search for in the sorted list (negative to quit)");
		int key = Integer.parseInt(keyboard.readLine());
		
		while(key >= 0)
		{
			ind = binSearch(list, key, 0, list.length-1);
			if (ind < 0)
				System.out.println("Sorry, " + key + " is not in the list. Again:");
			else
				System.out.println(key + " is found at index " + ind + " in the array.  Again:");
				
			key = Integer.parseInt(keyboard.readLine());
		}
		
		System.out.println("Thank you for playing.");
			
	}
}