public class BinarySearch
{
    /*
     * performs a binary search, See page 45 of the text.
     *  written in general using Comparable interface
     */
    public static void search(Comparable [] a, Comparable key)
    {
	int first = 0;
	int last = a.length - 1;
	int middle;
	boolean found = false;
	while(!found && first <= last)
	    {
		middle = (first + last)/2;
		System.out.println("first: " + first + " last: " + last + " middle: " + middle);
		if(key.equals(a[middle]) )
		    {
			found = true;
		    }
		else if(key.compareTo(a[middle]) < 0)
		    {
			last = middle - 1;
		    }
		else if (key.compareTo(a[middle]) >0 )
		    {
			first = middle + 1;
		    }
	    }
	if(found)
	    System.out.println(key + " was found");
	else
	    System.out.println(key + " was not found");
    }
		
		
    public static void main(String[] asd)
    {
	Comparable[] a = new Integer []{1, 2, 3, 12, 18, 23, 64, 87, 90, 93, 100};
	search(a, 18);			
	System.out.println();
	search(a, 33);			
	System.out.println();
    }
}