Algorithms

#include <stddef.h>

/*
 * Perform a binary lower bound search.
 *
 */

static size_t blsize;
static const void *skey;
static int (*cmpf)(const void *e1, const void *e2);

static void *lbnd(const void *base, size_t size)
{
	const char *p,*p1;
	int c;
	size_t n;

	if(size==0) return NULL;
	if(size==1)
	{
		c = (*cmpf)(skey,base);
		if(c<0)
			return NULL;
		else
			return (void *)base;
	}
	n = size >> 1;
	p = (char *)base + n*blsize;
	c = (*cmpf)(skey,p);
	if(c==0) return (void *)p;
	if(c<0)
	{
		return lbnd(base,n);
	}
	else
	{
		p1 = lbnd((char*)p + blsize,size - n - 1);
		if(p1==NULL)
			return (void *)p;
		else
			return (void *)p1;
	}
}

void *lbound(const void *key, const void *base0, size_t nmemb, size_t size, int (*compar)(const void *e1, const void *e2))
{
	blsize = size;
	cmpf = compar;
	skey = key;
	return lbnd(base0,nmemb);
}