Re: [9fans] bsearch ?

[Dan Cross <cross@math.psu.edu>]

> 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);
}