Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


home | help
bsearch(3C)		 Standard C Library Functions		   bsearch(3C)

       bsearch - binary	search a sorted	table

       #include	<stdlib.h>

       void  *bsearch(const  void  *key,  const	void *base, size_t nel,	size_t
       size, int (*compar)(const void *,const void *));

       The bsearch() function is a  binary  search  routine  generalized  from
       Knuth (6.2.1) Algorithm B. It returns a pointer into a table (an	array)
       indicating where	a datum	may be found or	a null pointer	if  the	 datum
       cannot  be found. The table must	be previously sorted in	increasing or-
       der according to	a comparison function pointed to by compar.

       The key argument	points to a datum instance to be sought	in the	table.
       The  base argument points to the	element	at the base of the table.  The
       nel argument is the number of elements in the table.  The size argument
       is the number of	bytes in each element.

       The  comparison	function pointed to by compar is called	with two argu-
       ments that point	to the key object and to an array element, in that or-
       der.  The  function  must  return  an  integer  less than, equal	to, or
       greater than 0 if the key object	is  considered,	 respectively,	to  be
       less than, equal	to, or greater than the	array element.

       The  bsearch()  function	 returns 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.

       The pointers to the key and the element at the base of the table	should
       be of type pointer-to-element.

       The comparison function need not	compare	every byte, so arbitrary  data
       may  be	contained in the elements in addition to the values being com-

       If the number of	elements in the	table is less than the	size  reserved
       for the table, nel should be the	lower number.

       The  bsearch()  function	 safely	 allows	 concurrent access by multiple
       threads to disjoint data, such as overlapping subtrees or tables.

       Example 1: Examples for searching a table containing pointers to	nodes.

       The example below searches a table containing pointers  to  nodes  con-
       sisting of a string and its length. The table is	ordered	alphabetically
       on the string in	the node pointed to by each entry.

       This program reads in strings and either	finds the  corresponding  node
       and prints out the string and its length, or prints an error message.

       #include	<stdio.h>
       #include	<stdlib.h>
       #include	<string.h>
       struct node {  /* these are stored in the table */
	   char	*string;
	   int length;
       static struct node table[] = {	 /* table to be	searched */
	   { "asparagus", 10 },
	   { "beans", 6	},
	   { "tomato", 7 },
	   { "watermelon", 11 },

	   struct node *node_ptr, node;
	   /* routine to compare 2 nodes */
	   static int node_compare(const void *, const void *);
	   char	str_space[20];	 /* space to read string into */

	   node.string = str_space;
	   while (scanf("%20s",	node.string) !=	EOF) {
	       node_ptr	= bsearch( &node,
		   table, sizeof(table)/sizeof(struct node),
		   sizeof(struct node),	node_compare);
	       if (node_ptr != NULL) {
		   (void) printf("string = %20s, length	= %d\n",
		       node_ptr->string, node_ptr->length);
	       } else {
		   (void)printf("not found: %20s\n", node.string);

       /* routine to compare two nodes based on	an  */
       /* alphabetical ordering	of the string field */
       static int
       node_compare(const void *node1, const void *node2) {
	   return (strcmp(
		   ((const struct node *)node1)->string,
		   ((const struct node *)node2)->string));

       See attributes(5) for descriptions of the following attributes:

       |      ATTRIBUTE	TYPE	     |	    ATTRIBUTE VALUE	   |
       |Interface Stability	     |Standard			   |
       |MT-Level		     |MT-Safe			   |

       hsearch(3C),  lsearch(3C), qsort(3C), tsearch(3C), attributes(5), stan-

SunOS 5.10			  6 Dec	2004			   bsearch(3C)


Want to link to this manual page? Use this URL:

home | help