public class TrinarySearch {
    /**
     * Task: Searches for a value in an array.
     *
     * @param a           an array of Comparable objects
     * @param desiredItem an item to search for
     * @param n           an integer > 0
     */
    public static <T extends Comparable<? super T>>
    boolean trinarySearch(T[] a, T desiredItem, int n) {
        // it is assumed that the data is already sorted
        return trinarySearch(a, 0, n - 1, desiredItem);
    } // end trinarySearch

    /**
     * Task: recursive trinarySearch search through an array of objects.
     *
     * @param a           an array of Comparable objects
     * @param desiredItem an item to search for
     * @param first       an integer >= 0
     * @param last        an integer > first and < a.length
     */

    public static <T extends Comparable<? super T>>
    boolean trinarySearch(T[] a, int first, int last, T desiredItem) {
        boolean found = false;


        if (first <= last)

        {
            int mid1 = (2 * first + last) / 3;
            int mid2 = (first + 2 * last) / 3;
            int compare1 = desiredItem.compareTo(a[mid1]);
            int compare2 = desiredItem.compareTo(a[mid2]);

            if (compare1 == 0 || compare2 == 0) {
                found = true;
            } else if (compare1 < 0) {
                found = trinarySearch(a, first, mid1 - 1, desiredItem);
            } else if (compare2 > 0) {
                found = trinarySearch(a, mid2 + 1, last, desiredItem);
            } else {
                found = trinarySearch(a, mid1 + 1, mid2 - 1, desiredItem);
            }
        }


        //   System.out.println("recursive trinarySearch method  - IMPLEMENT ME");


        return found;
    } // end trinarySearch