import java.util.Comparator;
import java.util.Arrays;

class BinarySearch {
    public static void main(String[] args) {
        Integer[] data = {-91, -70, 74, -18, 10, 86, 75, -49, -44, 73};
        System.out.println("Input: " + Arrays.toString(data));

        Comparator<Integer> c = (x,y) -> x - y;

        InsertionSort.sort(data, c);
        System.out.println("Sorted input: " + Arrays.toString(data));

        System.out.println("Found -49 at index = " + search(data, -49, c));
        System.out.println("Found -91 at index = " + search(data, -91, c));
        System.out.println("Found 86 at index = " + search(data, 86, c));
        System.out.println("Found 1 at index = " + search(data, 1, c));
    }

    /**
     * This method searches for the given element in the given
     * array.  It returns the index of the element if it is found,
     * otherwise, it returns -1.  The given array must be in
     * sorted order.
     * @param arr An array of type.
     * @param elem The element to search for.
     * @param c A comparator.
     * @return The index of the element, or -1.
     */
    public static <E> int search(E[] arr, E elem, Comparator<E> c) {
        return searchHelper(arr, elem, c, 0, arr.length - 1);
    }

    /**
     * This method searches for the given element in the given
     * array.  It returns the index of the element if it is found,
     * otherwise, it returns -1.  The given array must be in
     * sorted order.
     * @param arr An array.
     * @param elem The element to search for.
     * @param c A comparator.
     * @param lo The lower index bound of the search.
     * @param hi The upper index bound of the search.
     * @return The index of the element, or -1.
     */
    private static <E> int searchHelper(E[] arr, E elem, Comparator<E> c, int lo, int hi) {
        // base case #1: not found
        if (lo > hi) {
            return -1;
        }

        // calculate the midpoint
        int mid = (hi - lo) / 2 + lo;

        // is the midpoint the element we are looking for?
        int cmp = c.compare(elem, arr[mid]); // do a comparison

        // base case #2: found
        if (cmp == 0) {
            return mid;
        // recursive case #1: elem is to the left of mid
        } else if (cmp < 0) {
            return searchHelper(arr, elem, c, lo, mid - 1);
        // recursive case #2: elem is to the right of mid
        } else {
            return searchHelper(arr, elem, c, mid + 1, hi);
        }
    }
}

class InsertionSort {
    /**
     * Sorts the array in place using insertion sort.
     * @param data An array.
     * @param c A comparator.
     */
    public static <E> void sort(E[] data, Comparator<E> c) {
        int numSorted = 1;

        while (numSorted < data.length) {
            // this is the next unsorted value; copy it
            E temp = data[numSorted];

            // find where to insert it, shifting other values
            // over if necessary
            int i;
            for (i = numSorted; i > 0; i--) {
                if (c.compare(temp, data[i-1]) < 0) {
                    data[i] = data[i-1];
                } else {
                    break;
                }
            }
            // insert unsorted value into correct place
            data[i] = temp;
            numSorted++;
        }
    }
}