import java.util.Arrays;  // for Arrays.toString()

/**
 * Demonstration of the classic Binary Search
 * @author Hyrum D. Carroll
 * @version 0.2 (May 4, 2020)
 */
public class BinarySearch{

    /**
     * Binary search - recursively looks for an item in a sorted array by
     * reducing the search space to half the previous search space.
     * @param a SORTED array
     * @param item The search key
     * @return true is item is in a, false otherwise
     */
    public static boolean binarySearch( int[] a, int item ){
        return binarySearchRec( a, item, 0, a.length - 1);
    }

    /**
     * Binary search - recursively looks for an item in a sorted array by
     * reducing the search space to half the previous search space.
     * @param a SORTED array
     * @param item The search key
     * @param startIndex The first index in the remaining search space
     * @param endIndex The last index in the remaining search space
     * @return true is item is in a, false otherwise
     */
    private static boolean binarySearchRec( int[] a, int item, int startIndex, int endIndex ){

        // base case
        if( startIndex > endIndex ){
            // base case - no more search space left (item is not in a)
            return false;
        }

        /*
          Look at the middle element of an array.
          */

        int midIndex = (startIndex + endIndex) / 2;
        int midValue = a[ midIndex ];

        if( item > midValue ){
            // the number you're searching for is larger than the middle element, search the upper half.
            return binarySearchRec( a, item, midIndex + 1, endIndex);
        }else if( item < midValue ){
            // the number you're searching for is smaller than the middle element, search the lower half.
            return binarySearchRec( a, item, startIndex, midIndex - 1);
        }else{
            // the number is found.
            return true;
        }
    }


    public static void main( String[] args ){
        int[] array1 = {0,1,2,3,4,6,8,9};
        int[] array2 = {0,0,1,2,3,3,4,6,8,9};

        int search = 3;
        int[] array = array1;
        boolean result = false;

        array = array1;
        search = 3;
        result = binarySearch( array, search );
        System.out.println( "binarySearch( array="+Arrays.toString(array)+", search="+search+" ) returns "+result);

        array = array1;
        search = 7;
        result = binarySearch( array, search );
        System.out.println( "binarySearch( array="+Arrays.toString(array)+", search="+search+" ) returns "+result);

        /*
          {0,1,2,3,4,6,8,9};
                 ^ *******
                 7 > 3
          {0,1,2,3,4,6,8,9};
                     ^ ***
                     7 > 6
          {0,1,2,3,4,6,8,9};
                       ^
                       7 !> 8
                       7 < 8
         */

        array = array2;
        search = 3;
        result = binarySearch( array, search );
        System.out.println( "binarySearch( array="+Arrays.toString(array)+", search="+search+" ) returns "+result);
    }
}