// -----------------
// BinarySearch.java
// -----------------

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

final class BinarySearch {
    /**
     * O(1)     in space
     * O(log n) in time
     * Precondition: must be sorted
     */
    public static int eval(long[] a, int b, int e, long v) {
        assert b <= e;
        while (b != e) {
            final int  i = (b + e) >> 1;
            final long u = a[i];
            if (v < u)
                e = i;
            else if (v > u)
                b = i + 1;
            else
                return i;}
        return -(b + 1);}

    /**
     * O(1)     in space
     * O(log n) in time
     * Precondition: must be sorted
     */
    public static <T extends Comparable<? super T>> int eval(T[] a, int b, int e, T v) {
        assert b <= e;
        while (b != e) {
            final int i = (b + e) >> 1;
            final T   u = a[i];
            if (v.compareTo(u) < 0)
                e = i;
            else if (v.compareTo(u) > 0)
                b = i + 1;
            else
                return i;}
        return -(b + 1);}

    /**
     * O(1)     in space
     * O(log n) in time
     * Precondition: must be sorted
     */
    public static <T> int eval(T[] a, int b, int e, T v, Comparator<? super T> c) {
        assert b <= e;
        while (b != e) {
            final int i = (b + e) >> 1;
            final T   u = a[i];
            if (c.compare(v, u) < 0)
                e = i;
            else if (c.compare(v, u) > 0)
                b = i + 1;
            else
                return i;}
        return -(b + 1);}

    /**
     * O(1)                   in space
     * O(log n) -> O(n log n) in time
     * Precondition: must be sorted
     */
    public static <T extends Comparable<? super T>> int eval (List<? extends T> x, T v) {
        int b = 0;
        int e = x.size();
        while (b != e) {
            final int i = (b + e) >> 1;
            final T   u = x.get(i);
            if (v.compareTo(u) < 0)
                e = i;
            else if (v.compareTo(u) > 0)
                b = i + 1;
            else
                return i;}
        return -(b + 1);}

    /**
     * O(1)                   in space
     * O(log n) -> O(n log n) in time
     * Precondition: must be sorted
     */
    public static <T> int eval (List<? extends T> x, T v, Comparator<? super T> c) {
        int b = 0;
        int e = x.size();
        while (b != e) {
            final int i = (b + e) >> 1;
            final T   u = x.get(i);
            if (c.compare(v, u) < 0)
                e = i;
            else if (c.compare(v, u) > 0)
                b = i + 1;
            else
                return i;}
        return -(b + 1);}}

final class BinarySearchTest {
    public static void main (String[] args) {
        System.out.println("BinarySearch.java");

        {
        final long[] a = {2, 4, 6};
        assert Arrays.binarySearch(a, 1) == -1;
        assert Arrays.binarySearch(a, 3) == -2;
        assert Arrays.binarySearch(a, 4) ==  1;
        assert Arrays.binarySearch(a, 7) == -4;
        }

        {
        final long[] a = {2, 4, 6};
        assert BinarySearch.eval(a, 0, a.length, 1) == -1;
        assert BinarySearch.eval(a, 0, a.length, 3) == -2;
        assert BinarySearch.eval(a, 0, a.length, 4) ==  1;
        assert BinarySearch.eval(a, 0, a.length, 7) == -4;
        }

        {
        final Integer[] a = {2, 4, 6};
        assert Arrays.binarySearch(a, 1) == -1;
        assert Arrays.binarySearch(a, 3) == -2;
        assert Arrays.binarySearch(a, 4) ==  1;
        assert Arrays.binarySearch(a, 7) == -4;
        }

        {
        final Integer[] a = {2, 4, 6};
        assert BinarySearch.eval(a, 0, a.length, 1) == -1;
        assert BinarySearch.eval(a, 0, a.length, 3) == -2;
        assert BinarySearch.eval(a, 0, a.length, 4) ==  1;
        assert BinarySearch.eval(a, 0, a.length, 7) == -4;
        }

        {
        final Integer[]           a = {6, 4, 2};
        final Comparator<Integer> c =
            new Comparator<Integer> () {
                public int compare (Integer x, Integer y) {
                    return y - x;}};
        assert Arrays.binarySearch(a, 7, c) == -1;
        assert Arrays.binarySearch(a, 5, c) == -2;
        assert Arrays.binarySearch(a, 4, c) ==  1;
        assert Arrays.binarySearch(a, 1, c) == -4;
        }

        {
        final Integer[]           a = {6, 4, 2};
        final Comparator<Integer> c =
            new Comparator<Integer> () {
                public int compare (Integer x, Integer y) {
                    return y - x;}};
        assert BinarySearch.eval(a, 0, a.length, 7, c) == -1;
        assert BinarySearch.eval(a, 0, a.length, 5, c) == -2;
        assert BinarySearch.eval(a, 0, a.length, 4, c) ==  1;
        assert BinarySearch.eval(a, 0, a.length, 1, c) == -4;
        }

        {
        final List<Integer> x = Arrays.asList(2, 4, 6);
        assert Collections.binarySearch(x, 1) == -1;
        assert Collections.binarySearch(x, 3) == -2;
        assert Collections.binarySearch(x, 4) ==  1;
        assert Collections.binarySearch(x, 7) == -4;
        }

        {
        final List<Integer> x = Arrays.asList(2, 4, 6);
        assert BinarySearch.eval(x, 1) == -1;
        assert BinarySearch.eval(x, 3) == -2;
        assert BinarySearch.eval(x, 4) ==  1;
        assert BinarySearch.eval(x, 7) == -4;
        }

        {
        final List<Integer> x = Arrays.asList(6, 4, 2);
        final Comparator<Integer> c =
            new Comparator<Integer> () {
                public int compare (Integer x, Integer y) {
                    return y - x;}};
        assert Collections.binarySearch(x, 7, c) == -1;
        assert Collections.binarySearch(x, 5, c) == -2;
        assert Collections.binarySearch(x, 4, c) ==  1;
        assert Collections.binarySearch(x, 1, c) == -4;
        }

        {
        final List<Integer> x = Arrays.asList(6, 4, 2);
        final Comparator<Integer> c =
            new Comparator<Integer> () {
                public int compare (Integer x, Integer y) {
                    return y - x;}};
        assert BinarySearch.eval(x, 7, c) == -1;
        assert BinarySearch.eval(x, 5, c) == -2;
        assert BinarySearch.eval(x, 4, c) ==  1;
        assert BinarySearch.eval(x, 1, c) == -4;
        }

        System.out.println("Done.");}}