(^552) | Array-Based Lists
public booleanisThere(String item)
// Returns true if item is in the list; false otherwise
// Assumption: List items are in ascending order
{
int index = 0;
while(index < numItems
&& item.compareTo(listItems[index]) > 0)
index++;
return(index < numItems && item.compareTo(listItems[index]) == 0);
}
On average, searching a sorted list in this way takes the same number of iterations to find
an item as searching an unsorted list. The advantage of this new algorithm is that we find
out sooner if an item is missing. Thus it is slightly more efficient. Another search algorithm
exists that works only on a sorted list, but it is more complex: a binary search. However, the
extra complexity is worth the trouble.
Binary Search
Thebinary searchalgorithm on a sorted list is considerably faster both for finding an item
and for discovering that an item is missing. A binary search is based on the principle of suc-
cessive approximation. The algorithm divides the list in half (divides by 2—that’s why it’s
called abinarysearch) and decides which half to look in next. Division of the selected por-
tion of the list is repeated until the item is found or it is determined that the item is not pres-
ent in the list.
This method is analogous to the way in which we look up a name in a phone book (or word
in a dictionary). We open the phone book in the middle and compare the desired name with
one on the page that we turned to. If the name we’re seeking comes before this name, we con-
tinue our search in the left-hand section of the phone book. Otherwise, we continue in the
right-hand section of the phone book. We repeat this process until we find the name. If it is
not present, we realize that either we have misspelled the name or our phone book isn’t
complete. See Figure 11.8.
With this approach, we start with the whole list (indexes 0 through numItems – 1 ) and com-
pare our search value to the middle list item. If the search item is less than the middle list
item, we continue the search in the first half of the list. If the search item is greater than the
middle list item, we continue the search in the second half of the list. Otherwise, we have
found a match. We keep comparing and redefining the part of the list in which to look (the
search area) until we find the item or the search area is empty.
Let’s write the algorithm bounding the search area by the indexes firstand last. See
Figure 11.9.