tholm@uvicctr.UUCP (Terrence W. Holm) (08/26/88)
EFTH MINIX report #30 - August 1988 - bsearch(3)
There follows an implementation of bsearch(3) for
Minix. Please consider this public domain software.
A "man" page is included.
----------------------------------------------------------
echo x - bsearch.3
gres '^X' '' > bsearch.3 << '/'
XSUBROUTINES
X bsearch(3) - in core binary search
X
XINVOCATION
X char *bsearch( key, base, count, width, keycmp )
X char *key;
X char *base;
X unsigned int count;
X unsigned int width;
X int (*keycmp)();
X
XEXPLANATION
X Performs a binary search for a given <key> within a sorted
X table. The table contains <count> entries of size <width>
X and starts at <base>.
X
X Entries are compared using keycmp( key, entry ), each argument
X is a (char *), the function returns an int < 0, = 0 or > 0
X according to the order of the two arguments.
X
XRESULTS
X Bsearch(3) returns a pointer to the matching entry, if found,
X otherwise NULL is returned.
/
echo x - bsearch.c
gres '^X' '' > bsearch.c << '/'
X/* bsearch(3)
X *
X * Author: Terrence Holm Aug. 1988
X *
X *
X * Performs a binary search for a given <key> within a sorted
X * table. The table contains <count> entries of size <width>
X * and starts at <base>.
X *
X * Entries are compared using keycmp( key, entry ), each argument
X * is a (char *), the function returns an int < 0, = 0 or > 0
X * according to the order of the two arguments.
X *
X * Bsearch(3) returns a pointer to the matching entry, if found,
X * otherwise NULL is returned.
X */
X
X#define NULL (char *) 0
X
X
Xchar *bsearch( key, base, count, width, keycmp )
X char *key;
X char *base;
X unsigned int count;
X unsigned int width;
X int (*keycmp)();
X
X {
X char *mid_point;
X int cmp;
X
X while ( count > 0 )
X {
X mid_point = base + width * (count >> 1);
X
X cmp = keycmp( key, mid_point );
X
X if ( cmp == 0 )
X return( mid_point );
X
X if ( cmp < 0 )
X count >>= 1;
X else
X {
X base = mid_point + width;
X count = (count - 1) >> 1;
X }
X }
X
X return( NULL );
X }
/
----------------------------------------------------------
Edwin L. Froese
uw-beaver!ubc-cs!mprg!handel!froese
Terrence W. Holm
uw-beaver!uvicctr!tholm