Java Reference
In-Depth Information
chain contained 1000 nodes? In general, you need to traverse the chain, beginning at the first
node, until you reach the middle node. How will you know when you get there? If you know the
length of the chain, you can divide the length in half and count nodes as you traverse. The
details are not as important as a realization that it takes a bit of work to access the middle node.
After looking at the entry in the middle node, you probably need to ignore half of the chain and
search the other half. Do not change the chain when ignoring part of it. Remember that you want to
search the chain, not destroy it. Once you know which half to search, you must find its middle
node, again by traversing the chain. It should be clear to you that a binary search of a linked chain
of nodes would be challenging to implement and less efficient than a sequential search.
Note:
A binary search of a chain of linked nodes is impractical.
18.24
Choosing between a sequential search and a binary search.
You just saw that you should use a
sequential search to search a chain of linked nodes. But if you want to search an array of objects,
you need to know which algorithms are applicable. To use a sequential search, the objects must
have a method
equals
that ascertains whether two distinct objects are equal in some sense. Since
all objects inherit
equals
from the class
Object
, you must ensure that the objects you search have
overridden
equals
with an appropriate version. To perform a binary search on an array of objects,
on the other hand, the objects must have a
compareTo
method and the array must be sorted. If these
conditions are not met, you must use a sequential search.
If both search algorithms are applicable to your array, what search should you use? If the array
is small, you can simply use a sequential search. If the array is large and already sorted, a binary
search is typically much faster than a sequential search. But if the array is not sorted, should you
sort it and then use a binary search? The answer depends on how often you plan to search the array.
Sorting takes time, typically more time than a sequential search would. If you plan to search an
unsorted array only a few times, sorting the array so that you can use a binary search likely will not
save you time; use a sequential search instead.
Figure 18-8 summarizes the time efficiencies of the sequential search and the binary search.
Only the sequential search is applicable to unsorted data. The efficiencies given for the binary
search are for an array-based sorted list. For a large, sorted list, the binary search is typically much
faster than a sequential search.
FIGURE 18-8
The time efficiency of searching, expressed in Big Oh notation
Best Case
Average Case
Worst Case
Sequential search
(unsorted data)
Sequential search
(sorted data)
Binary search
(sorted array)
O(1)
O(
n
)
O(
n
)
O(1)
O(
n
)
O(
n
)
O(1)
O(log
n
)
O(log
n
)
