import Supporting.*;
import Exceptions.*;
import Supporting.Comparable;

public class BinarySearch
{
    /**
     * Performs the standard binary search
     * using two comparisons per level.
     * This is a driver that calls the recursive method.
     * @exception ItemNotFound if appropriate.
     * @return index where item is found.
     */
    public static int binarySearch( Comparable [ ] a, Comparable x )
                                    throws ItemNotFound
    {
        return binarySearch( a, x, 0, a.length -1 );
    }

    /**
     * Hidden recursive routine.
     */
    private static int binarySearch( Comparable [ ] a, Comparable x,
                                     int low, int high ) throws ItemNotFound
    {
        if( low > high )
            throw new ItemNotFound( "BinarySearch fails" );

        int mid = ( low + high ) / 2;

        if( a[ mid ].compares( x ) < 0 )
            return binarySearch( a, x, mid + 1, high );
        else if( a[ mid ].compares( x ) > 0 )
            return binarySearch( a, x, low, mid - 1 );
        else
            return mid;
    }

    // Test program
    public static void main( String [ ] args )
    {
        int SIZE = 8;
        Comparable [ ] a = new MyInteger [ SIZE ];
        for( int i = 0; i < SIZE; i++ )
            a[ i ] = new MyInteger( i * 2 );

        for( int i = 0; i < SIZE * 2; i++ )
        {
            try
            {
                System.out.println( "Found " + i + " at " +
                                     binarySearch( a, new MyInteger( i ) ) );
            }
            catch( ItemNotFound e )
              { System.out.println( i + " not found" ); }
        }
    }
}