public class BinarySearchTesting {
    /* Two versions of binary search */

    public static int search1 (int a [ ], int item) {
        /* program searches the sorted array a for item
           and returns the index if item or the
           location where item should be inserted to maintain ordering
        */

        /* Binary Search, Version 1 */
        int left = 0;
        int right = a.length - 1;
        int middle = (left + right + 1) / 2;  /* we must round up */
        while ((left <= right) && (a[middle] != item)) {
            if (a[middle] < item) 
                left = middle + 1;
            else
                right = middle - 1;
            middle = (left + right + 1) / 2;
        }
        
        return middle;
    }


    public static int search2 (int a [ ], int item) {
        /* program searches the sorted array a for item
           and returns the index if item or the
           location where item should be inserted to maintain ordering
        */

        /* Binary Search, Version 2 */
        int left = 0;
        int right = a.length;
        int middle = (left + right) / 2;  /* rounding does not matter here, 
                                             so we round down for simplicity */
        while ((left < right) && (a[middle] != item)) {
            if (a[middle] < item) 
                left = middle + 1;
            else
                right = middle;
            middle = (left + right) / 2;
        }
        return middle;
    }
    
    static void testBothSearches (int a [], int item) {
        /* use both search algorithms and print results */
        System.out.printf ("%5d  %5d", item, search1 (a, item));
        System.out.printf ("%8d\n", search2 (a, item));
    }  
    
    public static void main (String argv [ ]) {
        int a [ ] = new int [50];
        int index;
        
        /* initialize a as a sorted array */
        for (index = 0; index < a.length; index++)
            a[index] = 2*index;
        
        System.out.printf ("item  search1   search2\n\n");
        
        /* test boundary conditions */
        System.out.printf ("testing boundary conditions\n");
        testBothSearches (a, -3);
        testBothSearches (a, 0);
        testBothSearches (a, 2*a.length-2);
        testBothSearches (a, 2*a.length+10);
        
        /* testing found and not found within the array */
        System.out.printf ("\ntesting within the array\n");
        testBothSearches (a, 5);
        testBothSearches (a, 6);
        testBothSearches (a, 7);
        testBothSearches (a, 8);
        
    }
    
}