| Binary Search |
10 points
Introduction
The linear search that you coded recently could be slow. In searching for the zip code '08840' in a list of 932 New Jersey zip codes, you might have to wade through 931 of them before locating '08840' or realizing that '08840' is not in the list. A binary search, which you code here, can be much more efficient. The idea is this: first sort the list. Then compare the zip code you are looking for ('08840') with the element in the middle of the sorted list. If, say, '08840' is 'greater than' the middle element, you no longer need to consider the 'left half' of the list. Either '08840' is in the 'right half' of the list, or it isn't in the list.
Then adjust the middle of the list to mean the middle of the 'right half' of the sub-list. Again compare '08840' with the new middle element. If, say, '08840' is 'less than' the middle element, you no longer need to consider the 'right half' of the sub-list. Either '08840' is in the 'left half' of the sub-list, or it isn't in the sub-list.
And so on. Each time you carry out this procedure, you divide by 2 the number of elements you have to consider. Do you see why a binary search can be faster than a linear search?
Eventually the middle element of the list is equal to '08840', or if that never happens, you conclude that '08840' is simply not in the list.
Preparation
This program requires a sorted list. Right-click here to download a file (PQR-13.dat) containing a sorted list of 10,000 names from that wacky planet, PQR-13. (Wacky but rigid. They insist on six-letter names for everyone.) This file will be read in, in this binary search program.
private instance variables
Declare and create an 'ArrayList' object 'list'. You'll need a call to 'new ArrayList()'.
readNames()
This method reads in the 10,000 sorted names. This method is complete, though you will need to adjust the path of the input file with the sorted 10,000 names.
search()
Inside the parentheses in the first line of 'search', declare a String parameter 'sought' that the method receives from 'main()'.
Declare a boolean 'found', integers 'first', 'middle' and 'last', and Strings 'msg' and 'middleStr'. Set 'found' to 'false'. Give 'first' a value of 0, and use the 'size()' method of 'ArrayList' to set 'last' equal to the position of the last element in the ArrayList. (For example, since the ArrayList holds 10,000 zip codes, 'last' should be set to 9,999.)
Set up a DO - WHILE loop. Recall that the syntax is:
do
{
...
} while (some condition is true);
Use the 'get()' method of 'ArrayList' to get the 'middle' element of 'list' and assign it to 'middleStr'.
Inside the loop, set up an IF - ELSE IF - ELSE IF structure. Apply the 'compareTo()' method of 'String' to compare 'middleStr' with 'sought'.
If the result of this comparison is 0, 'middleStr' and 'sought' are equal. In this case, set 'found' to 'true'.
If the result of the comparison is negative, 'middleStr' comes before 'sought' in the ASCII or ANSI table. In this case, make an appropriate adjustment before you loop again.
If the result of the comparison is positive, 'middleStr' comes after 'sought'. In this case, make an appropriate adjustment before you loop again.
Continue looping until either you find what you're looking for, or you've looked everywhere, you haven't found it, and you give up.
After the loop ends, set up an IF - ELSE statement and let the user know whether or not 'sought' was found.
main()
Create an object of type 'BinarySearch' with a call to 'new BinarySearch()'. Call the 'showInputDialog()' method of the 'JOptionPane' class to find out what name the user wants to search for, and store her response in a String. Call the 'readNames()' method. Call the 'search()' method, sending in to 'search()' the name that the user is searching for.
Efficiency
Add a counter to your program that keeps track of how many times 'sought' is compared to another String. Run your binary search with 300, 1000, 3000 and 10,000 names. Make a table that shows how many comparisons are needed in each case to complete the binary search.
You can download BinarySearch.java to use as a starting point in writing your program.
You can download myBinarySearch.class, which will show how your program might run when it is done. Download the CLASS file. Also put a copy of 'sorted.dat' (the input file) in the same folder. Then open a Command Prompt and type 'java myBinarySearch'.