import java.util.ArrayList;

public class RecursiveBinarySearch
{
	private static ArrayList<String> words = new ArrayList<String>();

	public static void main(String[] args)
	{
		words.add("aardvark");
		words.add("ant");
		words.add("bees");
		words.add("cat");
		words.add("dog");
		words.add("fish");
		words.add("giraffe");
		words.add("horse");
		words.add("zebra");

		System.out.println(BinarySearch("fish", 0, words.size() - 1));
	}

	// This method uses a RECURSIVE binary search to look in the ArrayList
	// 'words' for a specific element (a String value); it returns the
	// INDEX of the string, if found, or -1 if not found; the parameter
	// 'first' is the starting position (index) of the search range in
	// the ArrayList, and 'last' is the ending index of the range
	private static int BinarySearch(String word, int first, int last)
	{
		int mid;

		if (last < first)
			return -1; // The element was NOT found
		else
		{
			// Find the midpoint (index) of the sublist
			mid = (first + last) / 2;

			if (word.equals(words.get(mid)))
				return mid; // The element WAS found

			else if (words.get(mid).compareTo(word) > 0)
				return BinarySearch(word, first, mid - 1);

			else
				return BinarySearch(word, mid + 1, last);
		}
	}
}