/** Let's implement a simple spell checker that uses a binary search * to find a word in a dictionary. This is pretty much the same Spell- * Checking class we did in CS 11. I've commented out the output. */ import java.io.*; public class Spell { private String [] dictionary; /** Read the system dictionary (list of words) and put the words in * my dictionary. There are 2 loops. One counts the words so we know how * big the dictionary is, and the second loop actually puts all these words * into our array. (Later, we will see a more efficient way to do this.) * We could have just looked at the dictionary ourselves and noticed it has * 25143 words and put that number in the code, but we'd rather have a more * flexible program. It's not a good idea to use "magic numbers". */ public Spell() throws IOException { // First, count the words in the dictionary (one per line). // Note that the name of the dictionary file may change (we could // ask the user for the location). BufferedReader in = new BufferedReader(new FileReader("/usr/dict/words")); int numWords = 0; while (true) { String word = in.readLine(); if (word == null) break; ++numWords; } // Allocate space for the array, and reopen the dictionary. dictionary = new String[numWords]; in = new BufferedReader(new FileReader("/usr/dict/words")); for (int i = 0; i < numWords; ++i) { dictionary[i] = in.readLine(); } // System.out.println("Done reading in dictionary."); } /** The idea here is to use a binary search. The variables left and right * will keep track of the endpoints of the search, and we guess in the * middle. If we are wrong, then we cut the search space in half, until * we find the word or conclude that it does not exist. */ public boolean findWord(String word) { int left = 0; int right = dictionary.length - 1; // Keep going until we run out of space. do { // System.out.println("I think the word is somewhere between " + // dictionary[left] + " and " + dictionary[right]); // Guess somewhere in the middle int middle = (left + right) / 2; // See what word it is and compare it to the word we're searching for. // If the word I'm looking for is greater than the middle word, then // we need to look in the right half of the array. if (word.compareToIgnoreCase(dictionary[middle]) > 0) { //System.out.println(" " + dictionary[middle] + // " is too low -- setting left to " + middle); left = middle; } // If the word I'm looking for is less than the middle word, then we // need to look in the left half of the array. else if (word.compareToIgnoreCase(dictionary[middle]) < 0) { //System.out.println(" " + dictionary[middle] + // " is too high -- setting right to " + middle); right = middle; } // Else we have a match! else { //System.out.println (" :) I found the word at position " + middle); return true; } } while (right >= left + 2); // The above test condition to continue looping means that we want to // keep trying to look in the dictionary as long as: right >= left + 2. // This means we still have some middle ground to divide. If this // condition weren't true, then the difference between the left and right // would only be 1, and there is no word in the middle to search for. // Make one last try to look at the extremes of the dictionary if (word.equalsIgnoreCase(dictionary[left]) || word.equalsIgnoreCase(dictionary[right])) { //System.out.println("Rare case of finding the word at the ends."); return true; } else { //System.out.println("Not even at the ends of the dictionary."); return false; } } }
