Java Reference
In-Depth Information
FIGURE 18-5
Ignoring one half of the data when the data is sorted
I don't need this half
of the topic. I'll just
throw it away.
We know this without looking at the elements beyond a[5] . We therefore can ignore these elements
as well as a[5] . Similarly, if the sought-after number were greater than a[5] (for example, if we
were looking for 10), we could ignore a[5] and all the elements before it.
Replacing the index 5 in the preceding example with whatever index is in the middle of the
array leads to a first draft of an algorithm for a binary search of an array:
Algorithm to search a[0] through a[n - 1] for desiredItem
mid
=
approximate midpoint between 0 and n - 1
if (desiredItem equals a[mid])
return true
else if (desiredItem < a[mid])
return the result of searching a[0] through a[mid - 1]
else if (desiredItem > a[mid])
return the result of searching a[mid + 1] through a[n - 1]
Notice that to
Search a[0] through a[n - 1]
you have to either
Search a[0] through a[mid - 1]
or
Search a[mid + 1] through a[n - 1]
These two searches of a portion of the array are smaller versions of the very task we are solving,
and so can be accomplished by calling the algorithm itself recursively.
Search WWH ::




Custom Search