import java.util.List;

/**
   A utility class with searching methods.

   @author Franck van Breugel
*/
public class Search
{
    /**
       Tests if a sublist of the given list contains the given element.
       The sublist starts at the given index.

       @param list the list.
       @param element the element.
       @pre. element != null
       @param begin begin index of sublist.
       @pre. begin >= 0
       @return true if the sublist of the given list contains the given element,
       false otherwise.
    */
    private static <T> boolean contains(T element, List<T> list, int begin)
    {
        boolean contains;
	if (begin >= list.size())
	{
	    contains = false;
	}
	else
	{
	    T first = list.get(begin);
	    if (element.equals(first))
	    {
		contains = true;
	    }
	    else
	    {
		contains = Search.contains(element, list, begin + 1);
	    }
	}
        return contains;
    }
    

    /**
       Tests if the given list contains the given element.

       @param list the list.
       @param element the element.
       @pre. element != null
       @return true if the the given list contains the given element,
       false otherwise.
    */
    public static <T> boolean contains(T element, List<T> list)
    {
	return Search.contains(element, list, 0);
    }

    /**
       Tests if a sublist of the given list contains the given element.
       The sublist consists of those elements whose index is greater than
       or equal to begin and smaller than end.

       @param list the list.
       @pre. list is sorted
       @param element the element.
       @pre. element != null
       @param begin index of the first element of the sublist.
       @pre. begin >= 0
       @param end index of the element following the last element of the sublist.
       @pre. end <= list.size()
       @return true if the sublist of the given list contains the given element,
       false otherwise.
    */
    private static <T extends Comparable<T>> boolean binary(T element, List<T> list, int begin, int end)
    {
        boolean contains;
	if (begin >= end)
	{
	    contains = false;
	}
	else
	{
	    int middle = (begin + end) / 2;
	    int comparison = element.compareTo(list.get(middle));
	    if (comparison == 0)
	    {
		contains = true;
	    }
	    else if (comparison < 0)
	    {
		contains = Search.binary(element, list, begin, middle);
	    }
	    else
	    {
		contains = Search.binary(element, list, middle + 1, end);
	    }
	}
        return contains;
    }

    /**
       Tests if the given list contains the given element.

       @param list the list.
       @pre. list is sorted
       @param element the element.
       @pre. element != null
       @return true if the given list contains the given element,
       false otherwise.
    */
    public static <T extends Comparable<T>> boolean binary(T element, List<T> list)
    {
	return Search.binary(element, list, 0, list.size());
    }
}