Java Reference
In-Depth Information
Question 3
List the comparisons that the previous method
search
makes while searching
for the object o in the array of objects
o1 o2 o3 o4 o5
Question 4
Implement at the client level a recursive method
search
by using only opera-
tions of the ADT list. The method should return true if a given item is in a given list.
Whether you implement a sequential search iteratively or recursively, the number of comparisons
will be the same. In the best case, you will locate the desired item first in the array. You will have
made only one comparison, and so the search will be O(1). In the worst case, you will search the
entire array. Either you will find the desired item at the end of the array or you will not find it at all.
In either event, you will have made
n
comparisons for an array of
n
entries. The sequential search in
the worst case is therefore O(
n
). Typically, you will look at about one-half of the entries in the
array. Thus, the average case is O(
n
/
2), which is just O(
n
).
Note:
The time efficiency of a sequential search of an array
Best case O(1)
Worst case: O(
n
)
Average case: O(
n
)
A sequential search of an unsorted array is rather easy to understand and to implement. When the
array contains relatively few entries, the search is efficient enough to be practical. However, when
the array contains many entries, a sequential search can be time-consuming. For example, imagine
that you are looking through a jar of coins for one minted during the year of your birth. A sequen-
tial search of 10 coins is not a problem. With 1000 coins, the search could be lengthy; with 1 mil-
lion coins, it is overwhelming. A faster search method would be welcome. Fortunately, faster
searches are possible.
Suppose that before you begin searching your coins, someone arranges them in sorted order by
their dates. If you search the sorted coins in Figure 18-4 sequentially for the date 1998, you would
look at the coins dated 1992, 1995, and 1997 before arriving at 1998. If, instead, you look for the
date 2000, you would look at the first five coins without finding it. Should you keep looking? If the
coins are sorted into ascending order and you have reached the one dated 2005, you will not find
2000 beyond it. If the coins were not sorted, you would have to examine all of them to see that 2000
was not present.
Note:
A sequential search can be more efficient if the data is sorted.
