| Recursive Binary Search |
8 points
Remember binary search? In a binary search, you begin with a sorted lists of names, numbers, or whatever the list is composed of. You also begin with something that you are trying to find in the list. You compare the element you are looking for (say "Tanway Kovach") with the middle element in the list. If they match, you're done, you found it. If they don't match, you look at whether "Tanway Kovach" would be to the left or the right of the middle element. If it would be to the left, as you continue searching you focus on only those elements that are in the left-hand half of the list. If "Tanway Kovach" would be to the right, as you continue searching you focus on only those elements that are in the right-hand half of the list. So with each iteration, you cut in half the number of elements that you have to search through in your quest for "Tanway Kovach". This makes the binary search very fast. In our text, p. 724, is a description of a non-recursive binary search program. You might want to consult this as you write a recursive version of binary search.
You will want to use the 'compareTo()' method of the String class to compare Strings in this program. 'compareTo' tells you whether one String would appear alphabetically before or after another String. 'compareTo' yields a negative integer if the first String comes alphabetically before the second String. For example, "lunch".compareTo("snack") yields a negative integer. For a second example, "lunch".compareTo("breakfast") yields a positive integer. Finally, "lunch".compareTo("lunch") yields a 0. You can use the integer that 'compareTo' returns in an IF statement.
You can download sorted.txt, a file with 10,000 names, in sorted order. You can also download RecursiveBinarySearch.java to use as a starting point in writing your program.
You can download sorted.txt and store it in C:/Temp. My class file, that you can download next, assumes that 'sorted.dat' is stored in C:/Temp. Next download myRecursiveBinarySearch.class, which will show how your program might run when it is done. Run the .class file from a DOS prompt like this: 'java myRecursiveBinarySearch'.