250 OTHER ALGORITHMIC TECHNIQUES
element each time, but the chances of that happening are very small. The down
side of this is that if our list happened to have the median element of each of
the subdivided pieces in the first location of that piece (the best case), our ran-
domness would not be likely to choose that element. So, the chance of the
worst or best cases occurring are both diminished.
We could apply this technique to searching as well. With a binary search,
there are some locations that require a number of failures before we check
them. A Sherwood version of “binary” search would randomly pick a location
to check between start and end. Sometimes we would wind up with a part
that is smaller than what it would be in a true binary search and sometimes
with a part that is larger. For example, with a list of 400 elements, instead of
choosing the 200th element for our comparison, we perhaps choose the 100th
element. If what we are looking for is smaller than the 100th element, our
Sherwood version will discard 75% of the elements instead of 50% for the stan-
dard algorithm. But if what we are looking for is larger than the 100th ele-
ment, we would only discard 25% of the elements. Again, our Sherwood
algorithm will sometimes do better and sometimes worse.
The basic idea is that a Sherwood algorithm reduces the time of the worst
case and increases the time of the best case. Just like Robin Hood in Sherwood
Forest, this technique robs from the rich (the best case) and gives to the poor
(the worst case).■ 9.2.5 Probabilistic Algorithm Comparison
Let's summarize the algorithms covered in this section. We saw that numerical
probabilistic algorithms will always supply an answer but that the longer the
algorithm runs, the more accurate the answer becomes. Monte Carlo algo-
rithms will always give an answer, but sometimes that answer will be wrong.
The longer that a Monte Carlo algorithm runs, the higher the probability the
answer will be correct. Multiple calls to a Monte Carlo algorithm can also
improve the results. Las Vegas algorithms never return a wrong answer but
might not return an answer if they are unable to find a correct one. Sherwood
techniques can be applied to any deterministic algorithm. They do not influ-
ence the correctness of the algorithm but rather reduce the chance of the
worst-case behavior. In doing so, however, they reduce the chance of the best-
case behavior as well.