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

public class RangeBinarySearch {
    // Returns the index of the first key in a[] that equals the search key, or -1 if no such key.
    // Complexity: O(log N), where N is the length of the array

    private final static int NOT_FOUND = -1;

    public static <Key> int firstIndexOf(Key[] a, Key key, Comparator<Key> comparator) {

        if (a == null || key == null || comparator == null)
            throw new java.lang.NullPointerException("No arguments can be empty.");

        int left = 0;
        int right = a.length - 1;

        while (left < right) {

            int mid = left + ((right - left) / 2);

            if (right == mid)
            	mid--;

            int c = comparator.compare(a[mid], key);

            if (c > 0)
                right = mid - 1;
            else if (c < 0)
                left = mid + 1;
            else {
                right = mid;
                if (right == left)
                	break;
            }
        }

        if (left == right && comparator.compare(a[left], key) == 0) {
        	//System.out.println("First index: " + left);
        	return left;
        }

        return NOT_FOUND; // NOT_FOUND = -1
    }



    // Returns the index of the last key in a[] that equals the search key, or -1 if no such key.
    // Complexity: O(log N)

    public static <Key> int lastIndexOf(Key[] a, Key key, Comparator<Key> comparator) {

        if (a == null || key == null || comparator == null)
            throw new java.lang.NullPointerException("No arguments can be empty.");

        int left = 0;
        int right = a.length - 1;

        while (left < right) {

            int mid = (left+right)/2;

           if (left == mid)
            	mid++;

            int c = comparator.compare(a[mid], key);

            if (c > 0)
                right = mid - 1;
            else if (c < 0)
                left = mid + 1;
            else {
                left = mid;
                if (left == right)
                	break;
            }
        }

        if (left == right && comparator.compare(a[right], key) == 0) {
        	//System.out.println("Last index: " + right);
        	return right;
        }

        return NOT_FOUND; // NOT_FOUND = -1

    }
}