import java.util.Collections;

public class BinarySearchList2<T extends Comparable<T>> extends SearchList<T>  {

    private boolean isSorted;
    public BinarySearchList2() {
        super();
        isSorted = true;
    }

    @Override
    public boolean add(T obj) {
        isSorted = false;
        return super.add(obj);
    }

    private int binarySearch(T target, int left, int right) {

        if (left>right)
            return -1;

        int mid = (left+right)/2;
        int diff = get(mid).compareTo(target);

        if (diff==0)
            return mid;
        if (diff<0)
            return binarySearch(target, mid+1, right);
        else
            return binarySearch(target, left,mid-1);
    }

    public int positionOf(T target) {
        if (!isSorted) {
            Collections.sort(this);
            isSorted = true;
        }
        return binarySearch(target, 0, this.size()-1);
    }

    public static void main(String[] args)    {
        SearchList<String> staff = new BinarySearchList2<String>();
        staff.add("Tom");
        staff.add("Dick");
        staff.add("Juliet");
        staff.add("Romeo");
        staff.add("Harry");

        System.out.println("Initial list:");
        for (String name : staff) {
            System.out.println(name);
        }

        String[] queries = {"Harry", "Tom", "Moe", "Curly"};

        for (String name : queries) {
            int pos = staff.positionOf(name);
            if (pos <0 )
                System.out.println(name + " not found");
            else
                System.out.println(name+" found @ "+pos);
        }
    }

}