Java Reference
In-Depth Information
Recall that two data fields of our list implementation in Chapter 13 are the array
list
, which
contains the list's entries, and the integer
numberOfEntries
, which is the number of entries.
VideoNote
Searching an array
The following implementation of
contains
was given in Segment 13.13. It uses a loop to search
the array
list
containing
numberOfEntries
objects having the generic type
T
for a particular object
anEntry
:
public boolean
contains(T anEntry)
{
boolean
found =
false
;
for
(
int
index = 0; !found && (index < numberOfEntries); index++)
{
if
(anEntry.equals(list[index]))
found =
true
;
}
// end for
return
found;
}
// end contains
The loop exits as soon as it locates the first entry in the array that matches the desired item. In this
case,
found
is true. On the other hand, if the loop examines all the entries in the list without finding
one that matches
anEntry
,
found
remains false. Figure 18-2 provides an example of these two out-
comes. For simplicity, our illustrations use integers.
FIGURE 18-2
An iterative sequential search of an array that (a) finds its target; (b)
does not find its target
(a) A search for 8
(b) A search for 6
Look at 9:
9
Look at 4:
9
Look at 9:
9
5
8
4
7
5
8
4
7
5
8
4
7
8
9, so continue searching.
6
9, so continue searching.
6
4, so continue searching.
Look at 7:
9
Look at 5:
9
Look at 5:
9
5
8
4
7
5
8
4
7
5
8
4
7
6
7, so continue searching.
8
5, so continue searching.
6
5, so continue searching.
No entries are left to consider, so the
search ends. 6 is not in the array.
Look at 8:
9
Look at 8:
9
4
5
8
4
7
5
8
7
8
8, so the search has found 8.
6
8, so continue searching.
