|
When it is known that a data set is in sorted order it is possible to
drastically increase the speed of a search operation in most cases.
The following section deals with an array-based implementation of the
binary search
algorithm.
In a later section we will look more closely at the binary search
tree
data structure and associated algorithm.
Both of these methods take advantage of the fact that the search space
is in some order to limit the area in which the target item is known
to reside.
An array-based binary search selects the median (middle) element in
the array and compares its value to that of the target value. Because
the array is known to be sorted, if the target value is less than the
middle value then the target must be in the first half of the array.
Likewise if the value of the target item is greater than that of the
middle value in the array, it is known that the target lies in the
second half of the array. In either case we can, in effect, ``throw
out'' one half of the search space with only one comparison.
Now, knowing that the target must be in one half of the array or the
other, the binary search examines the median value of the half in
which the target must reside. The algorithm thus narrows the search
area by half at each step until it has either found the target data or
the search fails.
The algorithm is easy to remember if you think about a child's
guessing game. Imagine I told you that I am thinking of a number
between 1 and 1000 and asked you to guess the number. Each time you
guessed I would tell you ``higher'' or ``lower.'' Of course you would
begin by guessing 500, then either 250 or 750 depending on my
response. You would continue to refine your choice until you got the
number correct.
| 
Search