stdlib/bsearch.c

   1 /* Copyright (C) 1991,92,97,2000,02 Free Software Foundation, Inc.
   2    This file is part of the GNU C Library.
   3
   4    The GNU C Library is free software; you can redistribute it and/or
   5    modify it under the terms of the GNU Lesser General Public
   6    License as published by the Free Software Foundation; either
   7    version 2.1 of the License, or (at your option) any later version.
   8
   9    The GNU C Library is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12    Lesser General Public License for more details.
  13
  14    You should have received a copy of the GNU Lesser General Public
  15    License along with the GNU C Library; if not, see
  16    <http://www.gnu.org/licenses/>.  */
  17
  18 #include <stdlib.h>
  19
  20
  21 /* Perform a binary search for KEY in BASE which has NMEMB elements
  22    of SIZE bytes each.  The comparisons are done by (*COMPAR)().  */
  23 void *
  24 bsearch (const void *key, const void *base, size_t nmemb, size_t size,
  25          int (*compar) (const void *, const void *))
  26 {
  27   size_t l, u, idx;
  28   const void *p;
  29   int comparison;
  30
  31   l = 0;
  32   u = nmemb;
  33   while (l < u)
  34     {
  35       idx = (l + u) / 2;
  36       p = (void *) (((const char *) base) + (idx * size));
  37       comparison = (*compar) (key, p);
  38       if (comparison < 0)
  39         u = idx;
  40       else if (comparison > 0)
  41         l = idx + 1;
  42       else
  43         return (void *) p;
  44     }
  45
  46   return NULL;
  47 }
  48 libc_hidden_def (bsearch)