**Previous:** 10.2 Improving Search - Sorting the Data

**Up:** 10 Sorting and Searching

**Next:** 10.4 An Example - Payroll Data Records

**Previous Page:** 10.2.3 Insertion Sort

**Next Page:** 10.4 An Example - Payroll Data Records

As we saw earlier, the linear search algorithm is
simple and convenient for small problems, but if the array is large and/or
requires many repeated searches, it makes good sense to have a more efficient
algorithm for searching an array.
Now that we know how to sort the elements of an array, we can make use of
that ordering to make our search more efficient.
In this section, we will present and
implement the * binary search* algorithm, a relatively simple and efficient
algorithm.

The algorithm is easily explained in terms of searching a dictionary for a word. In a dictionary, words are sorted alphabetically. For simplicity, let us assume there is only one page for all words starting with each letter. Let us assume we wish to search for a word starting with some particular letter.

We open the dictionary at some midway page, let us say a page on which words
start with * M*. If the value of our letter is * M*,
then we have found what we are looking for and the word is on the current
page. If the value of our letter is less than * M*,
we know that the word would be
found in the first half of the book,
i.e. we should search for the word in the pages
preceding the current page.
If the value of our letter is greater than * M*, we should
search the pages following the current page. In either case,
the effective size of the
dictionary to be searched is reduced to about half the original size.
We repeat the process in the appropriate half, opening to somewhere in
the middle of that and checking again.
As the process is repeated, the effective size of the dictionary to be searched
reduces by about half at each step until the word is found on a current page.

Binary search essentially follows this approach. For example, given a sorted array of items, say:

suppose we wish to search for the position of an element equal to12, 29, 30, 32, 35, 49

We use the ` binsrch()` function in an example program which repeatedly
searches for numbers input by the user. For each number, it either gives the
index where it is found or prints a message if it is not found. An array in
sorted form is initialized in the declaration. The code for this driver
is shown in Figure 10.15

Sample Session:

- ***Binary Search***
- The array is:
- 12 29 30 32 35 49
- Type a number, EOF to quit:
*12* - 12 found at array index 0
- Type a number, EOF to quit:
*23* - 23 not found in array
- Type a number, EOF to quit:
*34* - 34 not found in array
- Type a number, EOF to quit:
*45* - 45 not found in array
- Type a number, EOF to quit:
*30* - 30 found at array index 2
- Type a number, EOF to quit:
*29* - 29 found at array index 1
- Type a number, EOF to quit:
*'136D*

`
`

Sat Sep 3 06:58:41 HST 1994