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