bsearch() — Search arrays

Standards

Standards / Extensions	C or C++	Dependencies
ISO C POSIX.1 XPG4 XPG4.2 C99 Single UNIX Specification, Version 3	both

Format

#include <stdlib.h>

void *bsearch(const void *key, const void *base, size_t num, size_t size,
              int (*compare)(const void *element1, const void *element2));

General description

Performs a binary search of an array of num elements, each of size bytes.

The pointer base points to the initial element of the array to be searched. key points to the object containing the value being sought. The array must be sorted in ascending key sequence, according to the comparison function. Otherwise, undefined behavior occurs.

The compare parameter is a pointer to a function you must supply. It compares two array elements and returns a value specifying their relationship. The bsearch() function calls this function one or more times during the search, passing the key and the pointer to one array element on each call. The function compares the elements and then returns one of the following values:

Value: Meaning
< 0: Object pointed to by key is less than the array element.
= 0: Object pointed to by key is equal to the array element.
> 0: Object pointed to by key is greater than the array element.

Special Behavior for C++

Because C++ and C linkage conventions are incompatible, bsearch() cannot receive C++ function pointers. If you attempt to pass a C++ function pointer to bsearch(), the compiler will flag it as an error. To use the C++ bsearch() function, you must ensure that the compare function has C linkage by declaring it as extern “C”.

Returned value

If successful, bsearch() returns a pointer to a matching element of the array. If two or more elements are equal, the element pointed to is not specified.

If unsuccessful finding the key, bsearch() returns NULL.

Example

CELEBB01

⁄* CELEBB01

   This example performs a binary search on the argv array of pointers  o
   to the program arguments and finds the position of the argument PATH.
   It first removes the program name from argv, and then sorts the array
   alphabetically before calling bsearch().

   The functions compare1 and compare2 compare the values pointed to by
   arg1 and arg2, and they return the result to bsearch().

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

#ifdef __cplusplus  ⁄* the __cplusplus macro is   *⁄
extern "C" {        ⁄* automatically defined by the   *⁄
#endif              ⁄* C++⁄MVS compiler               *⁄
   int compare1(const void *arg1, const void *arg2);
   int compare2(const void *arg1, const void *arg2);
#ifdef __cplusplus
}
#endif


int main(int argc, char *argv[])
{
   char **result;
   char *key = "PATH";
   int i;
   argv++;
   argc--;

              ⁄* sort to ensure that the input is ordered *⁄
   qsort((char *)argv, argc, sizeof(char *), compare1);

   result = (char**)bsearch(key, (void *)argv, argc, sizeof(char *),
                            compare2);
   if (result != NULL) {
      printf("The key <%s> was found.\n",*result);
   }
   else printf("Match not found\n");
}

int compare1(const void *arg1, const void *arg2)
{
   return (strcmp(*(char **)arg1, *(char **)arg2));
}

int compare2(const void *arg1, const void *arg2) {
   return (strcmp((char *)arg1, *(char **)arg2));
}

Input

progname Is there PATH in this sentence?

Output