Java Reference
In-Depth Information
for the “average depth” of the leaf nodes. Define the total path length as the sum
of the levels for each node. The cost of an outcome is the level of the corresponding
node plus 1. The average cost of the algorithm is the average cost of the outcomes
(total path length=n). What is the tree with the least average depth? This is equiva-
lent to the tree that corresponds to binary search. Thus, binary search is optimal in
the average case.
While binary search is indeed an optimal algorithm for a sorted list in the worst
and average cases when searching a sorted array, there are a number of circum-
stances that might lead us to select another algorithm instead. One possibility is
that we know something about the distribution of the data in the array. We saw in
Section 9.1 that if each position in L is equally likely to hold X (equivalently, the
data are well distributed along the full key range), then an interpolation search is
(log log n) in the average case. If the data are not sorted, then using binary search
requires us to pay the cost of sorting the list in advance, which is only worthwhile if
many (at least O(log n)) searches will be performed on the list. Binary search also
requires that the list (even if sorted) be implemented using an array or some other
structure that supports random access to all elements with equal cost. Finally, if we
know all search requests in advance, we might prefer to sort the list by frequency
and do linear search in extreme search distributions, as discussed in Section 9.2.
15.3
Finding the Maximum Value
How can we find the ith largest value in a sorted list? Obviously we just go to the
ith position. But what if we have an unsorted list? Can we do better than to sort
it? If we are looking for the minimum or maximum value, certainly we can do
better than sorting the list. Is this true for the second biggest value? For the median
value? In later sections we will examine those questions. For this section, we
will continue our examination of lower bounds proofs by reconsidering the simple
problem of finding the maximum value in an unsorted list.
Here is a simple algorithm for finding the largest value.
/
**
@returnPositionoflargestvalueinarrayA
*
/
staticintlargest(int[]A){
intcurrlarge=0;//Holdslargestelementposition
for(inti=1;i<A.length;i++) //Foreachelement
if(A[currlarge]<A[i]) //ifA[i]islarger
currlarge=i; // rememberitsposition
returncurrlarge; //Returnlargestposition
}
Obviously this algorithm requires n comparisons. Is this optimal? It should be
intuitively obvious that it is, but let us try to prove it. (Before reading further you
might try writing down your own proof.)
