Searching - Data Structures and Abstractions with Java - page 456

18.16

Another approach. The binary search makes comparisons each time it locates the midpoint of the
array. Thus, to search n items, the binary search looks at the middle item and then searches n / 2
items. If we let t ( n ) represent the time requirement for searching n items, we find that at worst

t ( n ) = 1 + t ( n / 2) for n > 1
t (1) = 1

We encountered this recurrence relation in Segment 7.25 of Chapter 7. There, we showed that

t ( n ) = 1 + log 2 n
Thus, the binary search is O(log n ) in the worst case.

Searching an Unsorted Chain

18.17

Within a linked implementation of either the ADT list or the ADT sorted list, the method contains
would search a chain of linked nodes for the target. As you will see, a sequential search is really the
only practical choice. We begin with a chain whose data is unsorted, as typically would be the case
for the ADT list.

Regardless of a list's implementation, a sequential search of the list looks at consecutive
entries in the list, beginning with the first one, until either it finds the desired entry or it looks at all
entries without success. When the implementation is linked, however, moving from node to node is
not as simple as moving from one array location to another. Despite this fact, you can implement a
sequential search of a chain of linked nodes either iteratively or recursively and with the same effi-
ciency as that of a sequential search of an array.

VideoNote

Searching a linked chain

An Iterative Sequential Search of an Unsorted Chain
18.18

Figure 18-7 illustrates a chain of linked nodes that contain the list's entries. Recall from Segment 14.8
of Chapter 14 that firstNode is a data field of the class that implements the list. While it is clear that
a method can access the first node in this chain by using the reference firstNode , how can it access
the subsequent nodes? Since firstNode is a data field that always references the first node in the
chain, we would not want our search to alter it or any other aspect of the list. Thus, an iterative method
contains should use a local reference variable currentNode that initially contains the same reference
as firstNode . To make currentNode reference the next node, we would execute the statement
currentNode = currentNode.getNextNode();

FIGURE 18-7

A chain of linked nodes that contain the entries in a list

firstNode

The iterative sequential search has the following straightforward implementation:
public boolean contains(T anEntry)
{

boolean found = false ;
Node currentNode = firstNode;
while (!found && (currentNode != null ))
{