]>
Commit | Line | Data |
---|---|---|
fea681da MK |
1 | .\" Copyright 1993 David Metcalfe (david@prism.demon.co.uk) |
2 | .\" | |
93015253 | 3 | .\" %%%LICENSE_START(VERBATIM) |
fea681da MK |
4 | .\" Permission is granted to make and distribute verbatim copies of this |
5 | .\" manual provided the copyright notice and this permission notice are | |
6 | .\" preserved on all copies. | |
7 | .\" | |
8 | .\" Permission is granted to copy and distribute modified versions of this | |
9 | .\" manual under the conditions for verbatim copying, provided that the | |
10 | .\" entire resulting derived work is distributed under the terms of a | |
11 | .\" permission notice identical to this one. | |
c13182ef | 12 | .\" |
fea681da MK |
13 | .\" Since the Linux kernel and libraries are constantly changing, this |
14 | .\" manual page may be incorrect or out-of-date. The author(s) assume no | |
15 | .\" responsibility for errors or omissions, or for damages resulting from | |
16 | .\" the use of the information contained herein. The author(s) may not | |
17 | .\" have taken the same level of care in the production of this manual, | |
18 | .\" which is licensed free of charge, as they might when working | |
19 | .\" professionally. | |
c13182ef | 20 | .\" |
fea681da MK |
21 | .\" Formatted or processed versions of this manual, if unaccompanied by |
22 | .\" the source, must acknowledge the copyright and authors of this work. | |
4b72fb64 | 23 | .\" %%%LICENSE_END |
fea681da MK |
24 | .\" |
25 | .\" References consulted: | |
26 | .\" Linux libc source code | |
27 | .\" Lewine's _POSIX Programmer's Guide_ (O'Reilly & Associates, 1991) | |
28 | .\" 386BSD man pages | |
29 | .\" Modified Mon Mar 29 22:41:16 1993, David Metcalfe | |
30 | .\" Modified Sat Jul 24 21:35:16 1993, Rik Faith (faith@cs.unc.edu) | |
4b8c67d9 | 31 | .TH BSEARCH 3 2017-09-15 "" "Linux Programmer's Manual" |
fea681da MK |
32 | .SH NAME |
33 | bsearch \- binary search of a sorted array | |
34 | .SH SYNOPSIS | |
35 | .nf | |
36 | .B #include <stdlib.h> | |
68e4db0a | 37 | .PP |
9fb1e24a | 38 | .BI "void *bsearch(const void *" key ", const void *" base , |
a6e2f128 MK |
39 | .BI " size_t " nmemb ", size_t " size , |
40 | .BI " int (*" compar ")(const void *, const void *));" | |
fea681da MK |
41 | .fi |
42 | .SH DESCRIPTION | |
60a90ecd MK |
43 | The |
44 | .BR bsearch () | |
c6fa0841 MK |
45 | function searches an array of |
46 | .I nmemb | |
47 | objects, | |
48 | the initial member of which is pointed to by | |
49 | .IR base , | |
50 | for a member | |
51 | that matches the object pointed to by | |
52 | .IR key . | |
c13182ef | 53 | The size of each member |
c6fa0841 MK |
54 | of the array is specified by |
55 | .IR size . | |
fea681da MK |
56 | .PP |
57 | The contents of the array should be in ascending sorted order according | |
c6fa0841 MK |
58 | to the comparison function referenced by |
59 | .IR compar . | |
60 | The | |
61 | .I compar | |
62 | routine is expected to have two arguments which point to the | |
63 | .I key | |
fea681da | 64 | object and to an array member, in that order, and should return an integer |
c6fa0841 MK |
65 | less than, equal to, or greater than zero if the |
66 | .I key | |
67 | object is found, | |
fea681da MK |
68 | respectively, to be less than, to match, or be greater than the array |
69 | member. | |
47297adb | 70 | .SH RETURN VALUE |
60a90ecd MK |
71 | The |
72 | .BR bsearch () | |
73 | function returns a pointer to a matching member of the | |
c13182ef MK |
74 | array, or NULL if no match is found. |
75 | If there are multiple elements that | |
fea681da | 76 | match the key, the element returned is unspecified. |
b345bfca ZL |
77 | .SH ATTRIBUTES |
78 | For an explanation of the terms used in this section, see | |
79 | .BR attributes (7). | |
80 | .TS | |
81 | allbox; | |
82 | lb lb lb | |
83 | l l l. | |
84 | Interface Attribute Value | |
85 | T{ | |
86 | .BR bsearch () | |
87 | T} Thread safety MT-Safe | |
88 | .TE | |
847e0d88 | 89 | .sp 1 |
47297adb | 90 | .SH CONFORMING TO |
947693bb | 91 | POSIX.1-2001, POSIX.1-2008, C89, C99, SVr4, 4.3BSD. |
fea681da MK |
92 | .SH EXAMPLE |
93 | The example below first sorts an array of structures using | |
94 | .BR qsort (3), | |
95 | then retrieves desired elements using | |
63aa9df0 | 96 | .BR bsearch (). |
ba39b288 MK |
97 | .PP |
98 | .EX | |
fea681da MK |
99 | #include <stdio.h> |
100 | #include <stdlib.h> | |
101 | #include <string.h> | |
102 | ||
103 | struct mi { | |
b9f02710 MK |
104 | int nr; |
105 | char *name; | |
fea681da | 106 | } months[] = { |
b9f02710 MK |
107 | { 1, "jan" }, { 2, "feb" }, { 3, "mar" }, { 4, "apr" }, |
108 | { 5, "may" }, { 6, "jun" }, { 7, "jul" }, { 8, "aug" }, | |
109 | { 9, "sep" }, {10, "oct" }, {11, "nov" }, {12, "dec" } | |
fea681da MK |
110 | }; |
111 | ||
112 | #define nr_of_months (sizeof(months)/sizeof(months[0])) | |
113 | ||
c13182ef MK |
114 | static int |
115 | compmi(const void *m1, const void *m2) | |
b9f02710 MK |
116 | { |
117 | struct mi *mi1 = (struct mi *) m1; | |
118 | struct mi *mi2 = (struct mi *) m2; | |
119 | return strcmp(mi1\->name, mi2\->name); | |
fea681da MK |
120 | } |
121 | ||
c13182ef MK |
122 | int |
123 | main(int argc, char **argv) | |
b9f02710 MK |
124 | { |
125 | int i; | |
fea681da | 126 | |
b9f02710 MK |
127 | qsort(months, nr_of_months, sizeof(struct mi), compmi); |
128 | for (i = 1; i < argc; i++) { | |
129 | struct mi key, *res; | |
130 | key.name = argv[i]; | |
131 | res = bsearch(&key, months, nr_of_months, | |
132 | sizeof(struct mi), compmi); | |
133 | if (res == NULL) | |
31a6818e | 134 | printf("\(aq%s\(aq: unknown month\en", argv[i]); |
b9f02710 | 135 | else |
31a6818e | 136 | printf("%s: month #%d\en", res\->name, res\->nr); |
b9f02710 | 137 | } |
5bc8c34c | 138 | exit(EXIT_SUCCESS); |
fea681da | 139 | } |
ba39b288 | 140 | .EE |
fea681da | 141 | .\" this example referred to in qsort.3 |
47297adb | 142 | .SH SEE ALSO |
fea681da MK |
143 | .BR hsearch (3), |
144 | .BR lsearch (3), | |
145 | .BR qsort (3), | |
146 | .BR tsearch (3) |