Back to index

glibc  2.9
bsearch.c
Go to the documentation of this file.
00001 /* Copyright (C) 1991,92,97,2000,02 Free Software Foundation, Inc.
00002    This file is part of the GNU C Library.
00003 
00004    The GNU C Library is free software; you can redistribute it and/or
00005    modify it under the terms of the GNU Lesser General Public
00006    License as published by the Free Software Foundation; either
00007    version 2.1 of the License, or (at your option) any later version.
00008 
00009    The GNU C Library is distributed in the hope that it will be useful,
00010    but WITHOUT ANY WARRANTY; without even the implied warranty of
00011    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012    Lesser General Public License for more details.
00013 
00014    You should have received a copy of the GNU Lesser General Public
00015    License along with the GNU C Library; if not, write to the Free
00016    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00017    02111-1307 USA.  */
00018 
00019 #include <stdlib.h>
00020 
00021 
00022 /* Perform a binary search for KEY in BASE which has NMEMB elements
00023    of SIZE bytes each.  The comparisons are done by (*COMPAR)().  */
00024 void *
00025 bsearch (const void *key, const void *base, size_t nmemb, size_t size,
00026         int (*compar) (const void *, const void *))
00027 {
00028   size_t l, u, idx;
00029   const void *p;
00030   int comparison;
00031 
00032   l = 0;
00033   u = nmemb;
00034   while (l < u)
00035     {
00036       idx = (l + u) / 2;
00037       p = (void *) (((const char *) base) + (idx * size));
00038       comparison = (*compar) (key, p);
00039       if (comparison < 0)
00040        u = idx;
00041       else if (comparison > 0)
00042        l = idx + 1;
00043       else
00044        return (void *) p;
00045     }
00046 
00047   return NULL;
00048 }
00049 libc_hidden_def (bsearch)