xref: /freebsd/lib/libc/stdlib/bsearch.3 (revision e5b786625f7f82a1fa91e41823332459ea5550f9)
1.\" Copyright (c) 1990, 1991, 1993, 1994
2.\"	The Regents of the University of California.  All rights reserved.
3.\"
4.\" This code is derived from software contributed to Berkeley by
5.\" the American National Standards Committee X3, on Information
6.\" Processing Systems.
7.\"
8.\" Redistribution and use in source and binary forms, with or without
9.\" modification, are permitted provided that the following conditions
10.\" are met:
11.\" 1. Redistributions of source code must retain the above copyright
12.\"    notice, this list of conditions and the following disclaimer.
13.\" 2. Redistributions in binary form must reproduce the above copyright
14.\"    notice, this list of conditions and the following disclaimer in the
15.\"    documentation and/or other materials provided with the distribution.
16.\" 3. Neither the name of the University nor the names of its contributors
17.\"    may be used to endorse or promote products derived from this software
18.\"    without specific prior written permission.
19.\"
20.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30.\" SUCH DAMAGE.
31.\"
32.\"     @(#)bsearch.3	8.3 (Berkeley) 4/19/94
33.\"
34.Dd July 17, 2019
35.Dt BSEARCH 3
36.Os
37.Sh NAME
38.Nm bsearch
39.Nd binary search of a sorted table
40.Sh LIBRARY
41.Lb libc
42.Sh SYNOPSIS
43.In stdlib.h
44.Ft void *
45.Fn bsearch "const void *key" "const void *base" "size_t nmemb" "size_t size" "int (*compar) (const void *, const void *)"
46.Sh DESCRIPTION
47The
48.Fn bsearch
49function searches an array of
50.Fa nmemb
51objects, the initial member of which is
52pointed to by
53.Fa base ,
54for a member that matches the object pointed to by
55.Fa key .
56The size of each member of the array is specified by
57.Fa size .
58.Pp
59The contents of the array should be in ascending sorted order according
60to the comparison function referenced by
61.Fa compar .
62The
63.Fa compar
64routine
65is expected to have
66two arguments which point to the
67.Fa key
68object and to an array member, in that order, and should return an integer
69less than, equal to, or greater than zero if the
70.Fa key
71object is found, respectively, to be less than, to match, or be
72greater than the array member.
73See the
74.Fa int_compare
75sample function in
76.Xr qsort 3
77for a comparison function that is also compatible with
78.Fn bsearch .
79.Sh RETURN VALUES
80The
81.Fn bsearch
82function returns a pointer to a matching member of the array, or a null
83pointer if no match is found.
84If two members compare as equal, which member is matched is unspecified.
85.Sh EXAMPLES
86A sample program that searches people by age in a sorted array:
87.Bd -literal
88#include <assert.h>
89#include <stdint.h>
90#include <stdio.h>
91#include <stdlib.h>
92#include <string.h>
93
94struct person {
95	const char 	*name;
96	int 		age;
97};
98
99static int
100compare(const void *a, const void *b)
101{
102	const int *age;
103	const struct person *person;
104
105	age = a;
106	person = b;
107
108	return (*age - person->age);
109}
110
111int
112main(void)
113{
114	struct person *friend;
115	int age;
116	/* Sorted array */
117	const struct person friends[] = {
118		{ "paul", 22 },
119		{ "anne", 25 },
120		{ "fred", 25 },
121		{ "mary", 27 },
122		{ "mark", 35 },
123		{ "bill", 50 }
124	};
125	const size_t len = sizeof(friends) / sizeof(friends[0]);
126
127	age = 22;
128	friend = bsearch(&age, friends, len, sizeof(friends[0]), compare);
129	assert(strcmp(friend->name, "paul") == 0);
130	printf("name: %s\enage: %d\en", friend->name, friend->age);
131
132	age = 25;
133	friend = bsearch(&age, friends, len, sizeof(friends[0]), compare);
134
135	/*
136	 * For multiple elements with the same key, it is implementation
137	 * defined which will be returned
138	 */
139	assert(strcmp(friend->name, "fred") == 0 ||
140	    strcmp(friend->name, "anne") == 0);
141	printf("name: %s\enage: %d\en", friend->name, friend->age);
142
143	age = 30;
144	friend = bsearch(&age, friends, len, sizeof(friends[0]), compare);
145	assert(friend == NULL);
146	printf("friend aged 30 not found\en");
147}
148.Ed
149.Sh SEE ALSO
150.Xr db 3 ,
151.Xr lsearch 3 ,
152.Xr qsort 3
153.\" .Xr tsearch 3
154.Sh STANDARDS
155The
156.Fn bsearch
157function conforms to
158.St -isoC .
159