home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c065 / 1.ddi / CLIB1.ZIP / BSEARCH.C < prev    next >
Encoding:
C/C++ Source or Header  |  1990-06-07  |  3.0 KB  |  91 lines
  1. /*------------------------------------------------------------------------
  2.  * filename - bsearch.c
  3.  *
  4.  * function(s)
  5.  *        bsearch - binary search
  6.  *-----------------------------------------------------------------------*/
  7.  
  8. /*[]------------------------------------------------------------[]*/
  9. /*|                                                              |*/
  10. /*|     Turbo C Run Time Library - Version 3.0                   |*/
  11. /*|                                                              |*/
  12. /*|                                                              |*/
  13. /*|     Copyright (c) 1987,1988,1990 by Borland International    |*/
  14. /*|     All Rights Reserved.                                     |*/
  15. /*|                                                              |*/
  16. /*[]------------------------------------------------------------[]*/
  17.  
  18.  
  19. #include <stdlib.h>
  20.  
  21.  
  22. /*--------------------------------------------------------------------------*
  23.  
  24. Name    bsearch - binary search
  25.  
  26. Usage   void *bsearch(const void *key, const void * base,
  27.             size_t nelem, size_t width,
  28.             int (*fcmp)(const void *, const void *) );
  29.  
  30. Prototype in  stdlib.h
  31.  
  32. Description bsearch is a binary search  algorithm designed to search an
  33.     arbitrary  table of  information. The  entries in  the table
  34.     must  be  sorted  into  ascending  order  before  search is
  35.     called.
  36.  
  37.     . key points to  the item to be searched  for. ("the search
  38.     key")
  39.  
  40.     . base points to the base (0th element) of the search table
  41.  
  42.     . nelem contains the number of entries in the table
  43.  
  44.     . width contains the number of bytes in each entry
  45.  
  46.     . fcmp  points to  a user-written  comparison routine. That
  47.     routine compares 2  items and returns a value  based on the
  48.     comparison.
  49.     On each call to the comparison routine, the search function
  50.     pass 2 arguments: key, a pointer to the item being searched
  51.     for;  and elem,  a pointer   to the  element of  base being
  52.     compared.
  53.     fcmp  is free  to interpret  the search  key and  the table
  54.     entry any way it likes.
  55.  
  56. Return value  bsearch returns the address of the first entry in the table
  57.     that matches the search key.  If no match is found, bsearch
  58.     returns 0.
  59.  
  60.     In bsearch:
  61.  
  62.       If the key is     fcmp returns
  63.       -------------     ------------
  64.       Greater than *elem    An integer < 0
  65.       Identical to *elem    0
  66.       Less than *elem     An integer > 0
  67.  
  68. *---------------------------------------------------------------------------*/
  69. void *_CType bsearch(const void *key, const void *base, size_t nelem,
  70. size_t width, int _Cdecl (*fcmp)(const void *, const void *))
  71. {
  72.   char  *kmin, *probe;
  73.   int i, j;
  74.  
  75.   kmin = (char *) base;
  76.   while (nelem > 0){
  77.     i = nelem >> 1;
  78.     probe = kmin + i * width;
  79.     j = (*fcmp)(key, probe);
  80.     if (j == 0)
  81.       return(probe);
  82.     else if (j < 0)
  83.       nelem = i;
  84.     else  {
  85.       kmin = probe + width;
  86.       nelem = nelem - i - 1;
  87.     }
  88.   }
  89.   return(0);
  90. }
  91.