home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1995 August / NEBULA.bin / SourceCode / libcs / bsearch.c < prev    next >
Encoding:
Text File  |  1990-12-11  |  2.8 KB  |  77 lines
  1. /*
  2.  * Copyright (c) 1990 Carnegie Mellon University
  3.  * All Rights Reserved.
  4.  * 
  5.  * Permission to use, copy, modify and distribute this software and its
  6.  * documentation is hereby granted, provided that both the copyright
  7.  * notice and this permission notice appear in all copies of the
  8.  * software, derivative works or modified versions, and any portions
  9.  * thereof, and that both notices appear in supporting documentation.
  10.  *
  11.  * THE SOFTWARE IS PROVIDED "AS IS" AND CARNEGIE MELLON UNIVERSITY
  12.  * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
  13.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.  IN NO EVENT
  14.  * SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE FOR ANY SPECIAL, DIRECT,
  15.  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
  16.  * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF
  17.  * CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  18.  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  19.  *
  20.  * Users of this software agree to return to Carnegie Mellon any
  21.  * improvements or extensions that they make and grant Carnegie the
  22.  * rights to redistribute these changes.
  23.  *
  24.  * Export of this software is permitted only after complying with the
  25.  * regulations of the U.S. Deptartment of Commerce relating to the
  26.  * Export of Technical Data.
  27.  */
  28. /*
  29.  *    bsearch -- generic binary search, like qsort.
  30.  *
  31.  **********************************************************************
  32.  * HISTORY
  33.  * $Log:    bsearch.c,v $
  34.  * Revision 1.3  90/12/11  17:50:40  mja
  35.  *     Add copyright/disclaimer for distribution.
  36.  * 
  37.  * 09-May-87  Glenn Marcy (gm0w) at Carnegie-Mellon University
  38.  *    Added comment that a return of -1 is possible.
  39.  *
  40.  * 03-Feb-86  David Nichols (nichols) at Carnegie-Mellon University
  41.  *    Created.
  42.  *
  43.  **********************************************************************
  44.  */
  45.  
  46. /* Bsearch does a binary search on the array.  It returns either the index
  47.    of the matching element, the index of the largest element less than the
  48.    key, if such an element exists, otherwise returns -1 if not.  The caller
  49.    must use the compar function to determine if the key was found or not
  50.    when the index returned is non-negative. */
  51. int bsearch (base, nel, width, key, compar)
  52.     char *base;            /* start of the array to search */
  53.     int nel;            /* size of the array */
  54.     int width;            /* size of an element of the array */
  55.     char *key;            /* pointer to a key to find */
  56.     int (*compar)();        /* comparison routine like in qsort */
  57. {
  58.     int     l = 0;
  59.     int     u = nel - 1;
  60.     int     m;
  61.     int     r;
  62.  
  63.     /* Invariant: key > all elements in [0..l) and key < all elements in
  64.        (u..nel-1]. */
  65.     while (l <= u) {
  66.     m = (l + u) / 2;
  67.     r = (*compar) (key, base + (m * width));
  68.     if (r == 0)
  69.         return m;
  70.     else if (r < 0)
  71.         u = m - 1;
  72.     else
  73.         l = m + 1;
  74.     }
  75.     return u;            /* Which should == l - 1 */
  76. }
  77.