From mboxrd@z Thu Jan  1 00:00:00 1970
Message-Id: <200306301357.h5UDvK707520@augusta.math.psu.edu>
To: 9fans@cse.psu.edu
Subject: Re: [9fans] bsearch ?
In-Reply-To: Your message of "Mon, 30 Jun 2003 12:02:02 BST."
             <6d4520144abb8c805ef4d14c3b919320@snellwilcox.com>
From: Dan Cross <cross@math.psu.edu>
Date: Mon, 30 Jun 2003 09:57:20 -0400
Topicbox-Message-UUID: e163030c-eacb-11e9-9e20-41e7f4b1d025

> bsearch(2) is not in libc.
>
> I am sure it will not be for a good reason, but why?
> qsort is there so why not its friend?

Probably because it's not used that much.  Regardless, I once
wondered this myself and wrote a version.  Since binary search
is for some inexplicable reason one of those things that seems
is impossibly hard to get right, I'll paste it below; it
probably would be good to stick it in libc.

	- Dan C.

void *
bsearch(void *key, void *base, long nel, long width, int (*cmp)(void *, void *))
{
	char *bp;
	long m, l, r;
	int c;

	for (bp = base, l = 0, r = nel - 1; l <= r; ) {
		m = (l + r) / 2;
		c = cmp(key, bp + m * width);
		if (c == 0)
			return(bp + m * width);
		else if (c < 0)
			r = m - 1;
		else
			l = m + 1;
	}

	return(nil);
}