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 );
    }

    /**
     * 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 start The first index of the remaining search space
     * @param end The one past the last index of the remaining search space
     * @return true is item is in a, false otherwise
     */
    public static boolean binarySearchRec( int[] a, int item, int start, int end ){

        if( end <= start ){
            // not in the array
            return false;
        }

        int mid = (start + end) / 2; // index of the mid point

        if( a[mid] == item ){
            // found the item!
            return true;
        }else if( item > a[mid] ){
            // only look in the upper part of the search space
            int newStart = mid + 1;
            return binarySearchRec( a, item, newStart, end );
        }else{
            // only look in the lower part of the search space
            int newEnd = mid; // just mid, and not mid - 1 because end is not part of the search space
            return binarySearchRec( a, item, start, newEnd );
        }
    }


    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;

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

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

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