next up previous contents index Search
Next: Analysis Up: 0.2 Data Searching and Previous: Source Code

0.2.2 Binary Search

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.

Scott Gasch