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.