bsearch

Remonter à Stdlib.h - Index

Header File

stdlib.h

Category

Memory and String Manipulation Routines

Prototype

void *bsearch(const void *key, const void *base, size_t nelem, size_t width, int (_USERENTRY *fcmp)(const void *, const void *));

Description

Binary search of an array.

bsearch searches a table (array) of nelem elements in memory, and returns the address of the first entry in the table that matches the search key. The array must be in order. If no match is found, bsearch returns 0.

Remarque :  Because this is a binary search, the first matching entry is not necessarily the first entry in the table.

The type size_t is defined in stddef.h header file.

• nelem gives the number of elements in the table.
• width specifies the number of bytes in each table entry.

The comparison routine fcmp must be used with the _USERENTRY calling convention.

fcmp is called with two arguments: elem1 and elem2. Each argument points to an item to be compared. The comparison function compares each of the pointed-to items (*elem1 and *elem2), and returns an integer based on the results of the comparison.

• For bsearch, the fcmp return value is
• < 0 if *elem1 < *elem2
• == 0 if *elem1 == *elem2
• > 0 if *elem1 > *elem2

Return Value

bsearch returns the address of the first entry in the table that matches the search key. If no match is found, bsearch returns 0.

Example

 #include <stdlib.h>
 #include <stdio.h>
 typedef int (*fptr)(const void*, const void*);
 #define NELEMS(arr) (sizeof(arr) / sizeof(arr[0]))
 int numarray[] = {123, 145, 512, 627, 800, 933};
 int numeric (const int *p1, const int *p2)
 {
    return(*p1 - *p2);
 }
 #pragma argsused
 int lookup(int key)
 {
    int  *itemptr;
    /* The cast of (int(*)(const void *,const void*))
       is needed to avoid a type mismatch error at
       compile time */
    itemptr = (int *) bsearch (&key, numarray, NELEMS(numarray),
       sizeof(int), (fptr)numeric);
    return (itemptr != NULL);
 }
 int main(void)
 {
    if (lookup(512))
       printf("512 is in the table.\n");
    else
       printf("512 isn't in the table.\n");
    return 0;
 }

Portability

POSIX	Win32	ANSI C	ANSI C++
+	+	+	+