import java.util.ArrayList;
public class Search
{
	public static int scanSearch(ArrayList<Comparable> list, Comparable target)
	{
		int index = list.size() - 1;
		while (index >= 0 && !list.get(index).equals(target))
			index--;
			
		return index;
	}
	
	public static int binarySearch(ArrayList<Comparable> list, Comparable target)
	{
		if (list.isEmpty())
			return -1;
			
		return binarySearch(list, target, 0, list.size()-1);
	}
	
	private static int binarySearch(ArrayList<Comparable> list, Comparable target,
	                                int loIndex, int hiIndex)
	{
		if (loIndex > hiIndex)
			return -1;
			
		int middle = (loIndex + hiIndex) / 2;
		
		int comparison = list.get(middle).compareTo(target);
		
		if (comparison == 0)
			return middle;
			
		if (comparison > 0)
			return binarySearch(list, target, loIndex, middle-1);
			
		return binarySearch(list, target, middle+1, hiIndex);
	}
}