Programming in C

Character Strings, Structures, and Arrays 223

You can make use of the fact that your dictionary is in alphabetical order to develop a
more efficient lookupfunction.The first obvious optimization that comes to mind is in
the case that the word you are looking for does not exist in the dictionary.You can make
your lookupfunction “intelligent” enough to recognize when it has gone too far in its
search. For example, if you look up the word “active” in the dictionary defined in
Program 10.9, as soon as you reach the word “acumen,” you can conclude that “active” is
not there because, if it was, it would have appeared in the dictionary beforethe word
“acumen.”
As was mentioned, the preceding optimization strategy does help to reduce your
search time somewhat, but only when a particular word is notpresent in the dictionary.
What you are really looking for is an algorithm that reduces the search time in most
cases, not just in one particular case. Such an algorithm exists under the name of the
binary search.
The strategy behind the binary search is relatively simple to understand.To illustrate
how this algorithm works, take an analogous situation of a simple guessing game.
Suppose I pick a number from 1 to 99 and then tell you to try to guess the number in
the fewest number of guesses. For each guess that you make, I can tell you if you are too
low, too high, or if your guess is correct. After a few tries at the game, you will probably
realize that a good way to narrow in on the answer is by using a halving process. For
example, if you take 50 as your first guess, an answer of either “too high” or “too low”
narrows the possibilities down from 100 to 49. If the answer was “too high,” the number
must be from 1 to 49, inclusive; if the answer was “too low,” the number must be from
51 to 99, inclusive.
You can now repeat the halving process with the remaining 49 numbers. So if the
first answer was “too low,” the next guess should be halfway between 51 and 99, which is
75.This process can be continued until you finally narrow in on the answer. On the
average, this procedure takes far less time to arrive at the answer than any other search
method.
The preceding discussion describes precisely how the binary search algorithm works.
The following provides a formal description of the algorithm. In this algorithm, you are
looking for an element xinside an array M, which contains nelements.The algorithm
assumes that the array Mis sorted in ascending order.

Binary Search Algorithm

Step 1: Set lowto 0,highto n– 1.

Step 2: If low> high,xdoes not exist in Mand the algorithm terminates.

Step 3: Set midto (low+ high) / 2.

Step 4: If M[mid] < x, set lowto mid+ 1 and go to step 2.

Step 5: If M[mid] > x, set highto mid– 1 and go to step 2.

Step 6: M[mid] equals xand the algorithm terminates.

The division performed in step 3 is an integer division, so if lowis 0 and highis 49, the
val ue of midis 24.