bsearch(3C)															       bsearch(3C)

NAME

       bsearch() - binary search a sorted table

SYNOPSIS

DESCRIPTION

       is  a  binary search routine generalized from Knuth (6.2.1) Algorithm B.  It returns a pointer into a table indicating where a datum may be
       found.  The table must be previously sorted in increasing order according to a  provided  comparison  function.	 key  points  to  a  datum
       instance  to  be  sought  in  the table.  base points to the element at the base of the table.  nel is the number of elements in the table.
       size is the size of each element in the table.  compar is the name of the comparison function, which is	called	with  two  arguments  that
       point  to  the  elements being compared.  The function must return an integer less than, equal to, or greater than zero indicating that the
       first argument (the key) is to be considered less than, equal to, or greater than the second argument (the array element).

NOTES

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

       The comparison function need not compare every byte, so arbitrary data can be contained in the elements in addition  to	the  values  being
       compared.

       Although declared as type pointer-to-void, the value returned should be cast into type pointer-to-element.

RETURN VALUE

       A NULL pointer is returned if the key cannot be found in the table.

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.

       This code fragment 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>

	      #define TABSIZE  1000

	      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 *);
		  char str_space[20];	     /* space to read string into */
		  .
		  .
		  .
		  node.string = str_space;
		  while (scanf("%s", 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
",
			      node_ptr->string, node_ptr->length);
		      } else {
			  (void)printf("not found: %s
", 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)
	      struct node *node1, *node2;
	      {
		  return strcoll(((const struct node *)node1)->string,
			      ((const struct node *)node2)->string);
	      }

WARNINGS

       If  the table being searched contains two or more entries that match the selection criteria, a random entry is returned by as determined by
       the search algorithm.

SEE ALSO

       hsearch(3C), lsearch(3C), qsort(3C), tsearch(3C), thread_safety(5).

STANDARDS CONFORMANCE

																       bsearch(3C)