From 9891f38ddcca971fa21ab61e7a70832c8c877b0a Mon Sep 17 00:00:00 2001
From: Michael Hunteman <michael@huntm.net>
Date: Sat, 23 Sep 2023 12:53:46 -0500
Subject: Initial commit

---
 search.c | 61 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 61 insertions(+)
 create mode 100644 search.c

(limited to 'search.c')

diff --git a/search.c b/search.c
new file mode 100644
index 0000000..33218b0
--- /dev/null
+++ b/search.c
@@ -0,0 +1,61 @@
+#include <stdio.h>
+#include <math.h>
+
+int
+linear(int *haystack, int len, int needle)
+{
+	for (int i = 0; i < len; ++i) {
+		if (haystack[i] == needle) {
+			return 1;
+		}
+	}
+	return 0;
+}
+
+int
+binary(int *haystack, int low, int high, int needle)
+{
+	if (low > high) {
+		return 0;
+	}
+
+	int mid = low + (high - low) / 2;
+	if (haystack[mid] == needle) {
+		return 1;
+	} else if (haystack[mid] > needle) {
+		binary(haystack, low, mid - 1, needle);
+	} else {
+		binary(haystack, mid + 1, high, needle);
+	}
+}
+
+int
+square(int *breaks, int len, int needle)
+{
+	int jmp = floor(sqrt(len));
+	int i = jmp;
+	for (; i < len; i += jmp){
+		if (breaks[i]) {
+			break;
+		}
+	}
+	i -= jmp;
+	for (int j = 0; j <= jmp && i < len; ++i, ++j) {
+		if (breaks[i]) {
+			return i;
+		}
+	}
+	return 0;
+}
+
+int
+main()
+{
+	int haystack[5] = {0, 1, 2, 3, 4};
+	int breaks[5] = {0, 0, 1, 0, 0};
+	int len = sizeof(haystack) / sizeof(int);
+	printf("%d\n", linear(haystack, len, 3));
+	printf("%d\n", binary(haystack, 0, len, 3));
+	printf("%d\n", square(breaks, len, 3));
+	return 0;
+}
-- 
cgit v1.2.3