import java.util.Scanner;
public class BinarySearch
{
    public static final int NOT_FOUND = -1;
    public static int count = 0;

    /**
     * Performs the standard binary search
     * using two comparisons per level.
     * @return index where item is found, or NOT_FOUND.
     */
    public static <AnyType extends Comparable<? super AnyType>>
                  int binarySearch( AnyType [ ] a, AnyType x )
    {
        int low = 0;
        int high = a.length - 1;
        int mid;

        while( low <= high )
        {
            mid = ( low + high ) / 2;

            count++;

            if( a[ mid ].compareTo( x ) < 0 )
                low = mid + 1;
            else if( a[ mid ].compareTo( x ) > 0 )
                high = mid - 1;
            else
            {
                System.out.println("\ncount = " + count);
                return mid;
            }
        }

        System.out.println("\ncount = " + count);
        return NOT_FOUND;     // NOT_FOUND = -1
    }

    // Test program
    public static void main( String [ ] args )
    {
        int size, target, result;

        System.out.print("\nEnter the size of the array: ");
        Scanner scan = new Scanner(System.in);

        size = scan.nextInt();

        Integer [ ] a = new Integer [ size ];

        for( int i = 0; i < size; i++ )
            a[ i ] = i * 2;


        System.out.print("\nEnter an integer to search for: ");
        target = scan.nextInt();

        result = binarySearch(a, target);

        if (result != -1)
           System.out.println( "\n" + target + " Found at index " + result);
        else
           System.out.println( "\n" + target + " Not Found ");

        System.out.println();

    }
}