Searching and Sorting - Building Java Programs: A Back to Basics Approach - page 775

If you want to use the binarySearch method on either an array or a list, the data
must be in sorted order, because the method relies on the ordering to quickly find the
target value. If you call binarySearch on unsorted data, the results are undefined
and the algorithm doesn't guarantee that it will return the right answer.
Let's look at a short program that benefits from the speed of binary search. In the
game of Scrabble, players form words on a board using letter tiles to earn points.
Sometimes a player tries to spell a word that is not a legal word in the dictionary, so
another player “challenges” the word. The challenger looks up the word in the dic-
tionary, and depending on whether it is found, the move may be revoked from the
board. The following program helps resolve Scrabble word challenges by performing
binary searches for words in a dictionary file. The input file's words occur in sorted
order, so the list can be properly searched using Collections.binarySearch . (If
the file had not been sorted, we could have sorted it with Collections.sort ).
1 // Searches for words in a dictionary text file
2 // and reports each word's position in the file.
3
4 import java.io.*;
5 import java.util.*;
6
7 public class WordChallenge {
8 public static void main(String[] args)
9 throws FileNotFoundException {
10 System.out.println("Welcome to Scrabble word challenge!");
11
12 // read a sorted dictionary file into a List
13 Scanner in = new Scanner( new File("words.txt"));
14 List<String> words = new ArrayList<String>();
15 while (in.hasNext()) {
16 String word = in.next();
17 words.add(word);
18 }
19
20 // binary search the list for words
21 Scanner console = new Scanner(System.in);
22 while ( true ) {
23 System.out.print("Word to challenge (Enter to quit)? ");
24 String target = console.nextLine();
25 if (target.trim().length() == 0) {
26 break ;
27 }
28
29 int index = Collections.binarySearch(words, target);
30 if (index >= 0) {