#include <stdlib.h>
#include <limits.h>

size_t __bsearch(const void *key, const void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
{
	size_t baseidx = 0, tryidx;
	void *try;
	int sign;

	while (nel > 0) {
		tryidx = baseidx + nel/2;
		try = (char*)base + tryidx*width;
		sign = cmp(key, try);
		if (!sign) return tryidx;
		else if (sign < 0)
			nel /= 2;
		else {
			baseidx = tryidx + 1;
			nel -= nel/2 + 1;
		}
	}

	return ~baseidx;
}

void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *))
{
	size_t idx = __bsearch(key, base, nel, width, cmp);
	return idx > SSIZE_MAX ? NULL : (char*)base + idx*width;
}