import java.util.Comparator;
import java.util.List;

/**
 * Binary search wrapper over any type of user-defined collection.
 * It provides a finder for given element, but also finder of first
 * and last index in range of equal elements.
 */
public abstract class BinarySearch<E> {

    /**
     * Creates binary search wrapper over a list of comparable elements.
     */
    public static <T extends Comparable> BinarySearch<T> forList(final List<T> list) {
        return new BinarySearch<T>() {
            @Override
            @SuppressWarnings( {"unchecked"})
            protected int compare(final int index, final T element) {
                return list.get(index).compareTo(element);
            }

            @Override
            protected int getLastIndex() {
                return list.size() - 1;
            }
        };
    }

    /**
     * Creates binary search wrapper over a list with given comparator.
     */
    public static <T> BinarySearch<T> forList(final List<T> list, final Comparator<T> comparator) {
        return new BinarySearch<T>() {
            @Override
            @SuppressWarnings( {"unchecked"})
            protected int compare(final int index, final T element) {
                return comparator.compare(list.get(index), element);
            }

            @Override
            protected int getLastIndex() {
                return list.size() - 1;
            }
        };
    }

    /**
     * Creates binary search wrapper over an array.
     */
    public static <T extends Comparable> BinarySearch<T> forArray(final T[] array) {
        return new BinarySearch<T>() {
            @Override
            @SuppressWarnings( {"unchecked"})
            protected int compare(final int index, final T element) {
                return array[index].compareTo(element);
            }

            @Override
            protected int getLastIndex() {
                return array.length - 1;
            }
        };
    }

    /**
     * Creates binary search wrapper over an array with given comparator.
     */
    public static <T> BinarySearch<T> forArray(final T[] array, final Comparator<T> comparator) {
        return new BinarySearch<T>() {
            @Override
            @SuppressWarnings( {"unchecked"})
            protected int compare(final int index, final T element) {
                return comparator.compare(array[index], element);
            }

            @Override
            protected int getLastIndex() {
                return array.length - 1;
            }
        };
    }

    // ---------------------------------------------------------------- abstract

    /**
     * Compares element at <code>index</code> position with given object.
     */
    protected abstract int compare(int index, E element);

    /**
     * Returns index of last element in wrapped collection.
     */
    protected abstract int getLastIndex();

    // ---------------------------------------------------------------- find

    /**
     * Finds index of given element or negative value if element is not found.
     */
    public int find(final E element) {
        return find(element, 0, getLastIndex());
    }

    /**
     * Finds index of given element in inclusive index range. Returns negative
     * value if element is not found.
     */
    public int find(final E element, int low, int high) {
        while (low <= high) {
            int mid = (low + high) >>> 1;
            int delta = compare(mid, element);

            if (delta < 0) {
                low = mid + 1;
            } else if (delta > 0) {
                high = mid - 1;
            } else {
                return mid;
            }
        }
        // not found
        return -(low + 1);
    }

    // ---------------------------------------------------------------- first

    /**
     * Finds very first index of given element or negative value if element is not found.
     */
    public int findFirst(final E o) {
        return findFirst(o, 0, getLastIndex());
    }

    /**
     * Finds very first index of given element in inclusive index range. Returns negative
     * value if element is not found.
     */
    public int findFirst(final E o, int low, int high) {

        int ndx = -1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            int delta = compare(mid, o);

            if (delta < 0) {
                low = mid + 1;
            } else {
                if (delta == 0) {
                    ndx = mid;
                }
                high = mid - 1;
            }
        }

        if (ndx == -1) {
            return -(low + 1);
        }

        return ndx;
    }

    // ---------------------------------------------------------------- last

    /**
     * Finds very last index of given element or negative value if element is not found.
     */
    public int findLast(final E o) {
        return findLast(o, 0, getLastIndex());
    }

    /**
     * Finds very last index of given element in inclusive index range. Returns negative
     * value if element is not found.
     */
    public int findLast(final E o, int low, int high) {
        int ndx = -1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            int delta = compare(mid, o);

            if (delta > 0) {
                high = mid - 1;
            } else {
                if (delta == 0) {
                    ndx = mid;
                }
                low = mid + 1;
            }
        }

        if (ndx == -1) {
            return -(low + 1);
        }

        return ndx;
    }

}


import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;

class BinarySearchTest {

    protected List<String> list;
    protected BinarySearch<String> listBinarySearch;

    @BeforeEach
    void setUp() throws Exception {
        list = new ArrayList<>();
        list.add("aaa");    // 0
        list.add("bbb");
        list.add("ccc");
        list.add("ddd");    // 3
        list.add("ddd");    // 4
        list.add("ddd");    // 5
        list.add("eee");
        list.add("iii");    // 7
        list.add("iii");    // 8
        list.add("sss");

        listBinarySearch = BinarySearch.forList(list);
    }

    @Test
    void testFind() {
        assertEquals(0, listBinarySearch.find("aaa"));
        assertEquals(1, listBinarySearch.find("bbb"));
        assertEquals(2, listBinarySearch.find("ccc"));
        assertEquals(6, listBinarySearch.find("eee"));
        assertEquals(9, listBinarySearch.find("sss"));
        assertEquals(6, listBinarySearch.find("eee", 4, 6));

        assertTrue(listBinarySearch.find("aaaaa") < 0);
        assertTrue(listBinarySearch.find("aaa", 1, 4) < 0);
        assertTrue(listBinarySearch.find("eee", 4, 5) < 0);

        int ndx = listBinarySearch.find("ddd");
        assertTrue(ndx == 3 || ndx == 4 || ndx == 5);

        ndx = listBinarySearch.find("iii");
        assertTrue(ndx == 7 || ndx == 8);
    }

    @Test
    void testFindFirst() {
        assertEquals(0, listBinarySearch.findFirst("aaa"));
        assertEquals(1, listBinarySearch.findFirst("bbb"));
        assertEquals(2, listBinarySearch.findFirst("ccc"));
        assertEquals(6, listBinarySearch.findFirst("eee"));
        assertEquals(9, listBinarySearch.findFirst("sss"));
        assertEquals(6, listBinarySearch.findFirst("eee", 4, 6));

        assertTrue(listBinarySearch.findFirst("aaaaa") < 0);
        assertTrue(listBinarySearch.findFirst("aa") < 0);
        assertTrue(listBinarySearch.findFirst("aaa", 1, 4) < 0);
        assertTrue(listBinarySearch.findFirst("eee", 4, 5) < 0);

        assertEquals(3, listBinarySearch.findFirst("ddd"));
        assertEquals(7, listBinarySearch.findFirst("iii"));
    }

    @Test
    void testFindLast() {
        assertEquals(0, listBinarySearch.findLast("aaa"));
        assertEquals(6, listBinarySearch.findLast("eee"));
        assertEquals(9, listBinarySearch.findLast("sss"));
        assertEquals(6, listBinarySearch.findLast("eee", 4, 6));

        assertTrue(listBinarySearch.findLast("aaaaa") < 0);
        assertTrue(listBinarySearch.findLast("aaa", 1, 4) < 0);
        assertTrue(listBinarySearch.findLast("eee", 4, 5) < 0);

        assertEquals(5, listBinarySearch.findLast("ddd"));
        assertEquals(8, listBinarySearch.findLast("iii"));
    }

    @Test
    void testFindRange() {
        assertEquals(3, listBinarySearch.findFirst("ddd"));
        assertEquals(5, listBinarySearch.findLast("ddd", 3, 9));

        assertEquals(7, listBinarySearch.findFirst("iii"));
        assertEquals(8, listBinarySearch.findLast("iii", 7, 9));

        assertEquals(2, listBinarySearch.findFirst("ccc"));
        assertEquals(2, listBinarySearch.findLast("ccc", 2, 9));

    }
}