RE: [9fans] bsearch ?

RE: [9fans] bsearch ?

[Trickey, Howard W (Howard)]

> 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?

bsearch was not in the standard C library in our research Unix;
it must have been added to the standard by someone outside
the Labs.  So since we weren't using it, noone felt the need
to put it into the Plan 9 libc.

When I did APE, I needed to do a bsearch, so there is one
in /sys/src/ape/lib/ap/gen/bsearch.c, pretty much isomorphic
to the one just posted by Dan Cross.

- Howard

[9fans] bsearch ?

[steve.simon]

Hi,

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?

-Steve

Re: [9fans] bsearch ?

[Dan Cross]

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