man3/bsearch.3

   1 .\" Copyright 1993 David Metcalfe (david@prism.demon.co.uk)
   2 .\"
   3 .\" SPDX-License-Identifier: Linux-man-pages-copyleft
   4 .\"
   5 .\" References consulted:
   6 .\"     Linux libc source code
   7 .\"     Lewine's _POSIX Programmer's Guide_ (O'Reilly & Associates, 1991)
   8 .\"     386BSD man pages
   9 .\" Modified Mon Mar 29 22:41:16 1993, David Metcalfe
  10 .\" Modified Sat Jul 24 21:35:16 1993, Rik Faith (faith@cs.unc.edu)
  11 .TH BSEARCH 3 2021-08-27 GNU "Linux Programmer's Manual"
  12 .SH NAME
  13 bsearch \- binary search of a sorted array
  14 .SH LIBRARY
  15 Standard C library
  16 .RI ( libc ", " \-lc )
  17 .SH SYNOPSIS
  18 .nf
  19 .B #include <stdlib.h>
  20 .PP
  21 .BI "void *bsearch(const void *" key ", const void *" base ,
  22 .BI "              size_t " nmemb ", size_t " size ,
  23 .BI "              int (*" compar ")(const void *, const void *));"
  24 .fi
  25 .SH DESCRIPTION
  26 The
  27 .BR bsearch ()
  28 function searches an array of
  29 .I nmemb
  30 objects,
  31 the initial member of which is pointed to by
  32 .IR base ,
  33 for a member
  34 that matches the object pointed to by
  35 .IR key .
  36 The size of each member
  37 of the array is specified by
  38 .IR size .
  39 .PP
  40 The contents of the array should be in ascending sorted order according
  41 to the comparison function referenced by
  42 .IR compar .
  43 The
  44 .I compar
  45 routine is expected to have two arguments which point to the
  46 .I key
  47 object and to an array member, in that order, and should return an integer
  48 less than, equal to, or greater than zero if the
  49 .I key
  50 object is found,
  51 respectively, to be less than, to match, or be greater than the array
  52 member.
  53 .SH RETURN VALUE
  54 The
  55 .BR bsearch ()
  56 function returns a pointer to a matching member of the
  57 array, or NULL if no match is found.
  58 If there are multiple elements that
  59 match the key, the element returned is unspecified.
  60 .SH ATTRIBUTES
  61 For an explanation of the terms used in this section, see
  62 .BR attributes (7).
  63 .ad l
  64 .nh
  65 .TS
  66 allbox;
  67 lbx lb lb
  68 l l l.
  69 Interface       Attribute       Value
  70 T{
  71 .BR bsearch ()
  72 T}      Thread safety   MT-Safe
  73 .TE
  74 .hy
  75 .ad
  76 .sp 1
  77 .SH CONFORMING TO
  78 POSIX.1-2001, POSIX.1-2008, C89, C99, SVr4, 4.3BSD.
  79 .SH EXAMPLES
  80 The example below first sorts an array of structures using
  81 .BR qsort (3),
  82 then retrieves desired elements using
  83 .BR bsearch ().
  84 .PP
  85 .EX
  86 #include <stdio.h>
  87 #include <stdlib.h>
  88 #include <string.h>
  89
  90 struct mi {
  91     int nr;
  92     char *name;
  93 } months[] = {
  94     { 1, "jan" }, { 2, "feb" }, { 3, "mar" }, { 4, "apr" },
  95     { 5, "may" }, { 6, "jun" }, { 7, "jul" }, { 8, "aug" },
  96     { 9, "sep" }, {10, "oct" }, {11, "nov" }, {12, "dec" }
  97 };
  98
  99 #define nr_of_months (sizeof(months)/sizeof(months[0]))
 100
 101 static int
 102 compmi(const void *m1, const void *m2)
 103 {
 104     const struct mi *mi1 = m1;
 105     const struct mi *mi2 = m2;
 106     return strcmp(mi1\->name, mi2\->name);
 107 }
 108
 109 int
 110 main(int argc, char *argv[])
 111 {
 112     qsort(months, nr_of_months, sizeof(months[0]), compmi);
 113     for (int i = 1; i < argc; i++) {
 114         struct mi key;
 115         struct mi *res;
 116
 117         key.name = argv[i];
 118         res = bsearch(&key, months, nr_of_months,
 119                       sizeof(months[0]), compmi);
 120         if (res == NULL)
 121             printf("\(aq%s\(aq: unknown month\en", argv[i]);
 122         else
 123             printf("%s: month #%d\en", res\->name, res\->nr);
 124     }
 125     exit(EXIT_SUCCESS);
 126 }
 127 .EE
 128 .\" this example referred to in qsort.3
 129 .SH SEE ALSO
 130 .BR hsearch (3),
 131 .BR lsearch (3),
 132 .BR qsort (3),
 133 .BR tsearch (3)