From 54d463c220a76592165dcedc4639bf6f35b7d01c Mon Sep 17 00:00:00 2001 From: Bobby Bingham Date: Thu, 17 Jul 2014 21:21:20 -0500 Subject: Factor out binary_search --- bsearch.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) create mode 100644 bsearch.c (limited to 'bsearch.c') diff --git a/bsearch.c b/bsearch.c new file mode 100644 index 0000000..3c94d45 --- /dev/null +++ b/bsearch.c @@ -0,0 +1,24 @@ +#include + +#include "sorters.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; +} -- cgit v1.2.3