Efficient sorted array searching.

This function is compatible with the following targets:

ANSI

BeOS

EMB/RTOS

Mac OS

Palm OS

Win32

#include <stdlib.h>

void *bsearch(const void *key, const void *base, 

Parameters for this facility are:

key	const void *	What you are searching for
base	const void *	The array to be searched
num	size_t	Number of elements to be searched
size	size_t	Size of an array element
compare	const void *	A pointer to a function used for comparison

The bsearch() function efficiently searches a sorted array for an item using the binary search algorithm.

The key argument points to the item you want to search for.

The base argument points to the first byte of the array to be searched. This array must already be sorted in ascending order. This order is based on the comparison requirements of the function pointed to by the compare argument.

The num argument specifies the number of array elements to search.

The size argument specifies the size of an array element.

The compare argument is a pointer to a programmer-supplied function that is used to compare two elements of the array. That compare function takes two array element pointers as arguments. The first argument is the key that was passed to bsearch() as the first argument to bsearch(). The second argument is a pointer to an element of the array passed as the second argument to bsearch().

For explanation we will call the arguments search_key and array_element. This compare function compares the search_key to the array element. If the search_key and the array_element are equal, the function will return zero. If the search_key is less than the array_element, the function will return a negative value. If the search_key is greater than the array_element, the function will return a positive value.

bsearch() returns a pointer to the element in the array matching the item pointed to by key. If no match was found, bsearch() returns a null pointer (NULL).

"qsort"

// A simple telephone directory manager
// This program accepts a list of names and
// telephone numbers, sorts the list, then
// searches for specified names.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

// Maximum number of records in the directory.
#define MAXDIR 40

typedef struct
{
	char lname[15];							// keyfield--see comp() function
	char fname[15];
	char phone[15];
} DIRENTRY;						// telephone directory record

int comp(const DIRENTRY *, const DIRENTRY *);
DIRENTRY *look(char *);
DIRENTRY directory[MAXDIR];												// the directory itself
int reccount;							// the number of records entered

int main(void)
{
	DIRENTRY *ptr;
	int lastlen;
	char lookstr[15];
	
	printf("Telephone directory program.\n");
	printf("Enter blank last name when done.\n");

	reccount = 0;
	ptr = directory;
	do {
		printf("\nLast name: ");
		gets(ptr->lname);
		printf("First name: ");
		gets(ptr->fname);
		printf("Phone number: ");
		gets(ptr->phone);
		if ( (lastlen = strlen(ptr->lname)) > 0) {
			reccount++;
			ptr++;
		}
	} while ( (lastlen > 0) && (reccount < MAXDIR) );

	printf("Thank you.  Now sorting. . .\n");

	// sort the array using qsort()
	qsort(directory, reccount, 
				sizeof(directory[0]),(void *)comp);

	printf("Enter last name to search for,\n");
	printf("blank to quit.\n");
	printf("\nLast name: ");
	gets(lookstr);

	while ( (lastlen = strlen(lookstr)) > 0) {
		ptr = look(lookstr);
		if (ptr != NULL)
			printf("%s, %s: %s\n",
				ptr->lname,
				ptr->fname,
				ptr->phone);
		else	printf("Can't find %s.\n", lookstr);
		printf("\nLast name: ");
		gets(lookstr);
	}
	
	printf("Done.\n");
	
	return 0;
}

int comp(const DIRENTRY *rec1, const DIRENTRY *rec2)
{
	return (strcmp((char *)rec1->lname,
						(char *)rec2->lname));
}

// search through the array using bsearch()
DIRENTRY *look(char k[])	
{
	return (DIRENTRY *) bsearch(k, directory, reccount, sizeof(directory[0]), (void *)comp);
}
Output
Telephone directory program.
Enter blank last name when done.

Last name: Mation
First name: Infor
Phone number: 555-1212

Last name: Bell
First name: Alexander
Phone number: 555-1111

Last name: Johnson
First name: Betty
Phone number: 555-1010

Last name: 
First name: 
Phone number: 
Thank you.  Now sorting. . .
Enter last name to search for,
blank to quit.

Last name: Mation
Infor, Mation: 555-1212

Last name: Johnson
Johnson, Betty: 555-1010

Last name: 
Done.





[ First ]  [ Previous ]  [ Next ]  [ Last ]  [ Manuals ]







Visit the Metrowerks website at: http://www.metrowerks.com


For assistance contact Metrowerks Technical Support at: cw_support@metrowerks.com


Copyright © 2000, Metrowerks Corp. All rights reserved.





Last updated: August 16, 2000