import java.util.Scanner;


public class RecursiveApps {
	
	public static int sumToN(int n)
	{
		if (n < 2)
			return 1;
		else
			return n + sumToN(n-1);
	}
	
	public static int fact(int n)
	{
		if (n < 2)
			return 1;
		else 
			return n * fact(n - 1);
	}
	
	public static int twoP(int n)
	{
		return 0;
	}
	
	public static int linSearch(int[] a, int key, int low)
	{
		if (low >= a.length)
			return -1;
		else if (a[low] == key)
			return low;
		else
			return linSearch(a, key, low + 1);
	}
	
	public static int binSearch(int []a, int key) {
		int low = 0; // lowest possible location
		int high = a.length-1; // highest possible location
		int mid = (low + high) / 2; // low <= mid <= high
		// mid == high iff low == high
		while (low < high) {
			// determine on which side median resides:
			if (a[mid] < key) {
				low = mid + 1;
			} else {
				high = mid-1;
			}
			// low <= high
			// recompute median index
			mid = (low + high) / 2;
		}
		if (a[low] == key) return low;
		else return -1;		
	}
	
	public static int binSearch(int[] a, int key, int low, int high)
	{
		return 0;
	}
	
	public static void print(int []a)
	{
		for (int i = 0; i < a.length; i ++)
		{
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	
	public static void print(int []a, int low)
	{
		
	}

	private static int LISTLENGTH = 10;
	
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		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.insertionSort(list);
				
		print(list);
		print(list, 0);
		
		
		System.out.println("Enter a key to search for in the sorted list (negative to quit)");
		int key = scan.nextInt();
		
		while(key >= 0)
		{
			//ind = binSearch(list, key, 0, list.length-1);
			ind = binSearch(list, key);
			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 = scan.nextInt();
		}
		
		System.out.println("Thank you for playing.");
			
	}

	
	
	
	
}