Factor out binary_search

1 files changed, 24 insertions, 0 deletions

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 <stddef.h>
+
+#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;
+}