diff options
| -rw-r--r-- | Makefile | 4 | ||||
| -rw-r--r-- | include/container.h | 15 | ||||
| -rw-r--r-- | tests/binary_search.c | 33 |
3 files changed, 51 insertions, 1 deletions
@@ -6,7 +6,7 @@ CFLAGS := -g -Wall -Wextra -Wpedantic -Werror -Wno-language-extension-token tests: dynarray -dynarray: tests/dynarray.c tests/dynarray_struct.c tests/obscure.c +dynarray: tests/dynarray.c tests/dynarray_struct.c tests/obscure.c tests/binary_search.c $(CC) $(CFLAGS) -o $@ $< -DTT_CHAR ./dynarray $(CC) $(CFLAGS) -o $@ $< -DTT_SHORT @@ -19,6 +19,8 @@ dynarray: tests/dynarray.c tests/dynarray_struct.c tests/obscure.c ./dynarray $(CC) $(CFLAGS) -o $@ tests/obscure.c ./dynarray + $(CC) $(CFLAGS) -o $@ tests/binary_search.c + ./dynarray rm $@ diff --git a/include/container.h b/include/container.h index 775ffc2..7b2b8de 100644 --- a/include/container.h +++ b/include/container.h @@ -115,6 +115,7 @@ extern const qsort_cmp_t __qsort_cmps[64]; int array_compare(const void *const a1, const void *const a2, qsort_cmp_t comp); /// Exact copy of the array. you have to free the pointer as well. void* array_copy(void* old); +char array_binary_search(void* array, void* element, qsort_cmp_t cmp); /* ----------------------------------------------------------------- */ /* ----------------------LINKED LIST HEADER------------------------- */ @@ -340,6 +341,20 @@ int array_compare(const void *const a1, const void *const a2, qsort_cmp_t comp) /* //TODO!*/ /*}*/ +char array_binary_search(void* array, void* element, qsort_cmp_t cmp) { + ssize_t index1 = -1, + index2 = array_size(array); + if (index2 == 0) return 0; + while (1) { + ssize_t index3 = (index1+index2)/2; + if (index3 == index2 || index3 == index1 || index1 == index2) return 0; + int result = cmp(element, (byte*)array + array_element_size(array) * index3); + if (result == 0) return 1; + if (result < 0) index2 = index3; + else if (result > 0) index1 = index3; + } +} + #endif // CONTAINER_IMPLEMENTATION diff --git a/tests/binary_search.c b/tests/binary_search.c new file mode 100644 index 0000000..e3a973b --- /dev/null +++ b/tests/binary_search.c @@ -0,0 +1,33 @@ +#define CONTAINER_IMPLEMENTATION +#include "../include/container.h" + +#define prints(el) \ + do {printf("search %i: %s\n", el, (array_binary_search(array, &el, __default_int_cmp)) ? "true" : "false");} while(0) + +int main() { + int data[] = {9, 5, 2, 7, 6, 10, 5, 9, 7}; // no 8 there + int* array = array_new(int, sizeof(data)/sizeof(data[0])); + memcpy(array, data, sizeof(data)); + array_qsort_integral(array); + int minusten = -10; + int two = 2; + int eight = 8; + int five = 5; + int ten = 10; + int sixtynine = 69; + prints(minusten); + prints(two); + prints(five); + prints(eight); + prints(ten); + prints(sixtynine); + if (array_binary_search(array, &minusten, __default_int_cmp) == 1 || + array_binary_search(array, &two, __default_int_cmp) == 0 || + array_binary_search(array, &eight, __default_int_cmp) == 1 || + array_binary_search(array, &five, __default_int_cmp) == 0 || + array_binary_search(array, &ten, __default_int_cmp) == 0 || + array_binary_search(array, &sixtynine, __default_int_cmp) == 1 ) { + return EXIT_FAILURE; + } + return EXIT_SUCCESS; +} |