import java.util.Collections;

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

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

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

    public int positionOf(T target) {
        if (!isSorted) {
            Collections.sort(this);
            isSorted = true;
        }

        int left=0;
        int right=this.size()-1;

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

            if (diff==0)
                return mid;
            if (diff<0)
                left=mid+1; // search right half
            else
                right=mid-1; // search left half
        }
        return -1;
    }

    public static void main(String[] args)    {
        SearchList<String> staff = new BinarySearchList<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);
        }
   }

}