import java.io.*;
public class Search {

	private String [] data;

	// Create a new search object, we initialize data to the
	// contents of fileName. We assume that this file contains a
	// list of strings. The first line of the file is an integer, 
	// the number of lines that follow.
	Search(String fileName) throws Exception {
		
		FileReader f=new FileReader(fileName);
		BufferedReader br=new BufferedReader(f);

		String line; // current line of fileName

		// Find out how many elements follow and appropriately
		// initialize data
		line=br.readLine();
		int numLines=Integer.parseInt(line); // the number of lines that follow
		data=new String[numLines];
		
		// read the remainder of the file, placing 
		// consecutive elements in data
		int i=0;
		// lines 0,...,i-1 of the file are represented in
		// data[0],...,data[i-1]
		while((line=br.readLine())!=null && i<numLines){
			data[i]=line;
			i=i+1;
		}
	}

	// Pre: data is an array of strings, s is a String
	// Post: returns the last index of the element of data referencing
	// 	s if one exists, -1, otherwise
	static int linearSearch1(String s,String [] data){
		int position=-1; // the index of s in data if found, -1 if not
		int i=0; // Searched data[0],...,[i-1] so far
		while(i<data.length){
			if(data[i].equals(s)){
				position=i;
			}
			i=i+1;
		}
		return(position);
	}

	// Pre: data is an array of strings, s is a String
	// Post: returns the first index of the element of data referencing
	// 	s if one exists, data.length, otherwise
	// Optimization: Quit when we found the element
	static int linearSearch2(String s, String [] data){
		int i=0; // Searched data[0],...,[i-1] so far
		while(i<data.length && !data[i].equals(s)){
			i=i+1;
		}
		return(i);
	}

	// Pre: data is a sorted array of strings, s is a String
	// Post: returns the location that s should occupy if it
	//	appears in data.
	// Optimization: Quit when we found or passed the element
	static int linearSearch3(String s, String [] data){
		int i=0; // Searched data[0],...,[i-1] so far
		while(i<data.length && data[i].compareTo(s)<0){
			i=i+1;
		}
		return(i);
	}

	// Pre: data is a sorted array of strings, s is a String
	// Post: returns the location that s should occupy if it
	//	appears in data.
	// Optimization: use binary search
	static int binarySearch(String s, String [] data){
		int l=0; 
		int u=data.length;

		/* 
		We maintain all of the following conditions:
		0<=l<=u<=data.length
		data[0],...,data[l-1]<=s<=data[u],...,data[data.length-1]
		We don't know if data[l]<=s, it's possible that data[l]>s!!
		The first occurrence of s in data belongs somewhere in
		one of data[l],...,data[u].
		*/

		int mid; // the 'middle' of l,l+1,...,u
		while(l<u){
			mid=(l+u)/2; // Note: l<=mid<u (since l<u)
			if(data[mid].compareTo(s)<0)l=mid+1;
			else u=mid;
		}
		return(u);
	}

	public static void main(String [] args) throws Exception {
		Search s=new Search("words");
		s.searchAll("AAAAA");
		s.searchAll("ALGOL");
		s.searchAll("this");
		s.searchAll("thasssa");
		s.searchAll("zoos");
		s.searchAll("zzzzz");
	}
	public void searchAll(String w){
		String s="";
		s=searchString("linearSearch1",w,linearSearch1(w,data));
		s+=searchString("linearSearch2",w,linearSearch2(w,data));
		s+=searchString("linearSearch3",w,linearSearch3(w,data));
		s+=searchString("binarySearch",w,binarySearch(w,data));
		System.out.println(s);
	}
	String searchString(String method, String word, int result){
		return(method+"("+word+")="+result+"\n");
	}
}