Sams Teach Yourself C in 21 Days

The binary search algorithm is very efficient; it can search a large array quickly. Its oper-

ation is dependent on the array elements being arranged in ascending order. Here’s how

the algorithm works:

1. The key is compared to the element at the middle of the array. If there’s a match,
   the search is done. Otherwise, the key must be either less than or greater than the
   array element.


2. If the key is less than the array element, the matching element, if any, must be
   located in the first half of the array. Likewise, if the key is greater than the array
   element, the matching element must be located in the second half of the array.


3. The search is restricted to the appropriate half of the array, and then the algorithm
   returns to step 1.
   You can see that each comparison performed by a binary search eliminates half of the
   array being searched. For example, a 1,000-element array can be searched with only 10
   comparisons, and a 16,000-element array can be searched with only 14 comparisons. In
   general, a binary search requires n comparisons to search an array of 2nelements.

Sorting with qsort()....................................................................................

The library function qsort()is an implementation of the quicksort algorithm, invented

by C.A.R. Hoare. This function sorts an array into order. Usually the result is in ascend-

ing order, but qsort()can be used for descending order as well. The function prototype,

defined in stdlib.h, is

void qsort(void *base, size_t num, size_t size,

int (*cmp)(const void *element1, const void *element2));

The argument basepoints at the first element in the array,numis the number of elements

in the array, and sizeis the size (in bytes) of one array element. The argument cmpis a

pointer to a comparison function. The rules for the comparison function are the same as

for the comparison function used by bsearch(), described in the preceding section: You

often use the same comparison function for both bsearch()andqsort(). The function

qsort()has no return value.

Searching and Sorting: Two Demonstrations ................................................

Listing 19.5 demonstrates the use of qsort()andbsearch(). The program sorts and

searches an array of values. Note that the non-ANSI function getch()is used. If your

compiler doesn’t support it, you should replace it with the ANSI standard function

getchar().

550 Day 19

30 448201x-CH19 8/13/02 11:20 AM Page 550