diff options
author | Michael Hunteman <michael@huntm.net> | 2023-09-23 12:53:46 -0500 |
---|---|---|
committer | Michael Hunteman <michael@huntm.net> | 2023-10-21 21:48:03 -0500 |
commit | 9891f38ddcca971fa21ab61e7a70832c8c877b0a (patch) | |
tree | 1e820435b42c5c8187bb6d17b3ff1c204c933c1a /search.c |
Diffstat (limited to 'search.c')
-rw-r--r-- | search.c | 61 |
1 files changed, 61 insertions, 0 deletions
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; +} |