Searching - Data Structures and Abstractions with Java - page 446

Question 1 Write a method contains that returns the index of the first array entry that
equals anEntry . If the array does not contain such an entry, return - 1.

Question 2 Write a method contains that performs an iterative sequential search of a list
by using only operations of the ADT list. The method should return true if a given item is in
a given list.

A Recursive Sequential Search of an Unsorted Array
18.4

We begin a sequential search of an array by looking at the first entry in the array. If that entry is the
desired one, we end the search. Otherwise we search the rest of the array. Since this new search is
also sequential and since the rest of the array is smaller than the original array, we have a recursive
description of a solution to our problem. Well, almost. We need a base case. An empty array could
be the base case because it never contains the desired item.
For the array a , we search the n elements a[0] through a[n - 1] by beginning with the first ele-
ment, a[0] . If it is not the one we seek, we need to search the rest of the array—that is, we search
array elements a[1] through a[n - 1] . In general, we search the array elements a[first] through
a[n - 1] . To be even more general, we can search array elements a[first] through a[last] , where
first ≤ last .

18.5

The following pseudocode describes the logic of our recursive algorithm:
Algorithm to search a[first] through a[last] for desiredItem
if (there are no elements to search)
return false
else if (desiredItem equals a[first])
return true
else
return the result of searching a[first + 1] through a[last]
Figure 18-3 illustrates a recursive search of an array.

18.6

The method that implements this algorithm will need parameters first and last . To spare the client
the detail of providing values for these parameters, and to allow the method contains to have the
same header as it did in Segment 18.3, we implement the algorithm as a private method search that
contains invokes. Since we again assume the array-based list implementation from Chapter 13, the
array list takes the place of the array a in the previous algorithm, and numberOfEntries is the num-
ber of elements to search. Because list and numberOfEntries are data fields of the class that imple-
ments the list, they are not parameters of the methods that follow.

/** Searches the list for anEntry. */
public boolean contains(T anEntry)
{

return search(0, numberOfEntries - 1, anEntry);
} // end contains
/** Searches list[first] through list[last] for desiredItem.
@param first an integer index >= 0 and < numberOfEntries
@param last an integer index >= 0 and < numberOfEntries
@param desiredItem the object to be found
@return true if desiredItem is found */