bsearch.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <stddef.h>

#include "common.h"

/* If a matching element exists, returns index of one of them.
   If none exists, returns index where such an element should be inserted. */
size_t binary_search(const char *needle, char *haystack, size_t nmel, size_t width, cmpfun cmp)
{
	size_t baseidx = 0;
	while (nmel) {
		size_t tryidx = baseidx + nmel / 2;
		char *try = haystack + tryidx * width;
		int sign = cmp(try, needle);
		if (!sign) return tryidx;
		else if (sign < 0) {
			baseidx = tryidx + 1;
			nmel -= nmel / 2 + 1;
		}
		else {
			nmel /= 2;
		}
	}
	return baseidx;
}