package search.list;

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

public class BinarySearch {

    public static > int search(List list,
            T target) {
        return search(list, target, new DefaultComparator());
    }

    public static  int search(List list, T target,
            Comparator comparator) {
        return searchRecursive(list, target, comparator, 0, list.size());
    }

    public static  int searchRecursive(List list, T target,
            Comparator comparator, int start, int last) {
        if (start > last) {
            return -1;  // not found
        }
        int half = (start + last) / 2;
        int comp = comparator.compare(target, list.get(half)); 
        if (comp < 0) {
            /*
             *        It may be contained in this range.
             *                 <-------->
             * [X][X][X]...[X][X][X]...[X][X][X]...[X][X][X]...[X][X]
             *                 ^           ^           ^
             *               start        half        last
             */
            return searchRecursive(list, target, comparator, start, half);
        } else if (comp > 0) {
            /*
             *                       It may be contained in this range.
             *                                <----->
             * [X][X][X]...[X][X][X]...[X][X][X]...[X][X][X]...[X][X]
             *                 ^           ^           ^
             *               start        half        last
             */
            return searchRecursive(list, target, comparator, half + 1, last);
        } else {  // comp == 0
            return half;  // found
        }
    }

    public static void main(String... args) {
        final int MAX = 100;
        List list = new ArrayList();
        while (list.size() < MAX) {
            list.add((int) (Math.random() * Integer.MAX_VALUE));
        }
        Integer sample = list.get((int) Math.random() * list.size());
        Collections.sort(list);

        System.out.println("Look for `" + sample + "'");
        System.out.println("in the list " + list);

        int result = search(list, sample);
        assert (result >= 0);
        assert (sample.equals(list.get(result)));

        System.out.println("Result index: " + result);
    }

    private static class DefaultComparator>
            implements Comparator {

        @Override
        public int compare(T a, T b) {
            return a.compareTo(b);
        }

    }
}