Programming and Problem Solving with Java

SEARCHING EXPERIMENTS

ProblemWrite an applet that lets the user experiment with looking for items in a list
and trying to determine which searching algorithm is being used. The number of com-
parisons is a metric that is often employed to measure searching efficiency, so the
applet should display the number of comparisons performed in determining whether
the value was present in the list.

Background In Chapter 11, three searching algorithms were presented and discussed:
a sequential search in a sorted list, a sequential search in an unsorted list, and a binary
search. A sequential search begins by looking at the first item in the list and continues
looking at each successive item until it finds the item or reaches the end of the list. A
sequential search in a sorted list can recognize when the search has reached the place
where the item would be if it were present and thus can stop at that point. A binary
search assumes that the list items are sorted; it begins looking in the middle of the list
and successively throws away half of the list with each comparison until it finds the
item or there is nowhere else to look.

BrainstormingThe problem doesn’t state which of the three algorithms is used. We can
wait to decide that later, because the primary processing does not depend on the
algorithm. The classes in this solution are found in the problem statement: a list of
items, an item, and a counter to keep track of the number of comparisons. Because the
applet runs from a web page, we know that the input and output will be from the GUI
components on the screen. Thus we must have an input text field and an output label.
Where there is an input text field, a button is always lurking nearby.

ScenariosThe user enters an item, and the applet reports whether the item is in the list
and how many comparisons were required to make that determination. Where there is a
button, there is a listener and an event loop. What actions must be executed within the
event handler? The item must be read, the list must be searched, and the results must be
given to the user. The user may input another item or quit the process by closing the
applet window (if an applet viewer is being used) or going to another Web page.
What must the applet do to set up this situation within the event handler? For one
thing, it must generate a list to be searched. Because the problem statement says

List

Item

GUI components (label, textfield, button)

Applet

CASE STUDY^671