bsearch.3p (6177B)
- '\" et
- .TH BSEARCH "3P" 2017 "IEEE/The Open Group" "POSIX Programmer's Manual"
- .\"
- .SH PROLOG
- This manual page is part of the POSIX Programmer's Manual.
- The Linux implementation of this interface may differ (consult
- the corresponding Linux manual page for details of Linux behavior),
- or the interface may not be implemented on Linux.
- .\"
- .SH NAME
- bsearch
- \(em binary search a sorted table
- .SH SYNOPSIS
- .LP
- .nf
- #include <stdlib.h>
- .P
- void *bsearch(const void *\fIkey\fP, const void *\fIbase\fP, size_t \fInel\fP,
- size_t \fIwidth\fP, int (*\fIcompar\fP)(const void *, const void *));
- .fi
- .SH DESCRIPTION
- The functionality described on this reference page is aligned with the
- ISO\ C standard. Any conflict between the requirements described here and the
- ISO\ C standard is unintentional. This volume of POSIX.1\(hy2017 defers to the ISO\ C standard.
- .P
- The
- \fIbsearch\fR()
- function shall search an array of
- .IR nel
- objects, the initial element of which is pointed to by
- .IR base ,
- for an element that matches the object pointed to by
- .IR key .
- The size of each element in the array is specified by
- .IR width .
- If the
- .IR nel
- argument has the value zero, the comparison function pointed to by
- .IR compar
- shall not be called and no match shall be found.
- .P
- The comparison function pointed to by
- .IR compar
- shall be called with two arguments that point to the
- .IR key
- object and to an array element, in that order.
- .P
- The application shall ensure that the comparison function pointed to by
- .IR compar
- does not alter the contents of the array. The implementation may
- reorder elements of the array between calls to the comparison function,
- but shall not alter the contents of any individual element.
- .P
- The implementation shall ensure that the first argument is always a
- pointer to the key.
- .P
- When the same objects (consisting of width bytes, irrespective of their
- current positions in the array) are passed more than once to the
- comparison function, the results shall be consistent with one another.
- That is, the same object shall always compare the same way with the
- key.
- .P
- The application shall ensure that the function returns an integer less
- than, equal to, or greater than 0 if the
- .IR key
- object is considered, respectively, to be less than, to match, or to be
- greater than the array element. The application shall ensure that the
- array consists of all the elements that compare less than, all the
- elements that compare equal to, and all the elements that compare
- greater than the
- .IR key
- object, in that order.
- .SH "RETURN VALUE"
- The
- \fIbsearch\fR()
- function shall return a pointer to a matching member of the array, or a
- null pointer if no match is found. If two or more members compare
- equal, which member is returned is unspecified.
- .SH ERRORS
- No errors are defined.
- .LP
- .IR "The following sections are informative."
- .SH "EXAMPLES"
- The example below searches a table containing pointers to nodes
- consisting of a string and its length. The table is ordered
- alphabetically on the string in the node pointed to by each entry.
- .P
- The code fragment below reads in strings and either finds the
- corresponding node and prints out the string and its length, or prints
- an error message.
- .sp
- .RS 4
- .nf
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- .P
- #define\ TABSIZE 1000
- .P
- struct node { /* These are stored in the table. */
- char *string;
- int length;
- };
- struct node table[TABSIZE]; /* Table to be searched. */
- .
- .
- .
- {
- struct node *node_ptr, node;
- /* Routine to compare 2 nodes. */
- int node_compare(const void *, const void *);
- .
- .
- .
- while (scanf("%ms", &node.string) != EOF) {
- node_ptr = (struct node *)bsearch((void *)(&node),
- (void *)table, TABSIZE,
- sizeof(struct node), node_compare);
- if (node_ptr != NULL) {
- (void)printf("string = %20s, length = %d\en",
- node_ptr->string, node_ptr->length);
- } else {
- (void)printf("not found: %s\en", node.string);
- }
- free(node.string);
- }
- }
- /*
- This routine compares two nodes based on an
- alphabetical ordering of the string field.
- */
- int
- node_compare(const void *node1, const void *node2)
- {
- return strcoll(((const struct node *)node1)->string,
- ((const struct node *)node2)->string);
- }
- .fi
- .P
- .RE
- .SH "APPLICATION USAGE"
- The pointers to the key and the element at the base of the table should
- be of type pointer-to-element.
- .P
- The comparison function need not compare every byte, so arbitrary data
- may be contained in the elements in addition to the values being
- compared.
- .P
- In practice, the array is usually sorted according to the comparison
- function.
- .SH RATIONALE
- The requirement that the second argument (hereafter referred to as
- .IR p )
- to the comparison function is a pointer to an element of the array
- implies that for every call all of the following expressions are
- non-zero:
- .sp
- .RS 4
- .nf
- ( (char *)p - (char *)base ) % width == 0
- (char *)p >= (char *)base
- (char *)p < (char *)base + nel * width
- .fi
- .P
- .RE
- .SH "FUTURE DIRECTIONS"
- None.
- .SH "SEE ALSO"
- .IR "\fIhcreate\fR\^(\|)",
- .IR "\fIlsearch\fR\^(\|)",
- .IR "\fIqsort\fR\^(\|)",
- .IR "\fItdelete\fR\^(\|)"
- .P
- The Base Definitions volume of POSIX.1\(hy2017,
- .IR "\fB<stdlib.h>\fP"
- .\"
- .SH COPYRIGHT
- Portions of this text are reprinted and reproduced in electronic form
- from IEEE Std 1003.1-2017, Standard for Information Technology
- -- Portable Operating System Interface (POSIX), The Open Group Base
- Specifications Issue 7, 2018 Edition,
- Copyright (C) 2018 by the Institute of
- Electrical and Electronics Engineers, Inc and The Open Group.
- In the event of any discrepancy between this version and the original IEEE and
- The Open Group Standard, the original IEEE and The Open Group Standard
- is the referee document. The original Standard can be obtained online at
- http://www.opengroup.org/unix/online.html .
- .PP
- Any typographical or formatting errors that appear
- in this page are most likely
- to have been introduced during the conversion of the source files to
- man page format. To report such errors, see
- https://www.kernel.org/doc/man-pages/reporting_bugs.html .