// Arup Guha
// 1/30/07
// Example using an array of Strings to illustrate array syntax.
import java.util.*;
import java.io.*;

public class FindWord {
	
	public static void main(String[] args) throws IOException {
		
		Scanner stdin = new Scanner(System.in);
		
		// Get the dictionary file from the user.
		System.out.println("Enter your dictionary file.");
		String filename = stdin.next();
		Scanner fin = new Scanner(new File(filename));
		
		// Read in the whole sorted dictionary.		
		int numwords = fin.nextInt();
		String[] dictionary = new String[numwords];
			
		for (int i=0; i<dictionary.length; i++)
			dictionary[i] = fin.next();
		fin.close();
			
		// Ask the user for a word to check.
		System.out.println("Enter a word, all lower case to search for."); 
		String target = stdin.next();
			
		// Search for the word and print out an appropriate message.
		if (FindWord.search(target, dictionary))
			System.out.println(target+" IS a word.");
		else
			System.out.println("Sorry, "+target+" is not a word.");
		
	}
	
	// This method returns true iff the String word appears in the
	// array alphalist as one of the elements exactly. Specifically,
	// the method performs a binary search.
	public static boolean search(String word, String[] alphalist) {
		
		// Setting the bounds of the search space in the array.
		int low = 0;
		int high = alphalist.length;
		
		boolean found = false;
		
		// Loop until there is no search space.
		while (low <= high) {
			
			// This is halfway through the search space.
			int mid = (low+high)/2;
			
			// Decide which "half of the array" to look in next.
			if (word.compareTo(alphalist[mid]) > 0)
				low = mid+1;
			else if (word.compareTo(alphalist[mid]) < 0)
				high = mid-1;
				
			// This means we hit the word exactly.
			else {
				found = true;
				break;
			}
		}
		
		return found;
	}
}