44 lines
1.9 KiB
C
44 lines
1.9 KiB
C
/* This file has the implementation of the function for bubble sort. */
|
|
/* Include guards + include statements. */
|
|
#ifndef BINARY_SEARCH_C
|
|
#define BINARY_SEARCH_C
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
#include "binary_search.h"
|
|
#endif /* BINARY_SEARCH_C */
|
|
|
|
/* Note that if the comparison function is NULL, the array pointer is NULL or the search value is NULL, then the function will quit. */
|
|
/* Note that the comparison function should return 1 if the second argument is larger than the first, zero if they're both equal and -1 otherwise. */
|
|
/* The array's length should be passed in the length argument. */
|
|
/* Size should match a single object's size, and should be > 0. */
|
|
/* The function returns BINARY_SEARCH_INDEX_NOT_FOUND on error or not found, otherwise will return the index of the value. */
|
|
int binary_search(void *array, void *value, int (*comparison_function)(const void*, const void*), const int length, size_t size) {
|
|
/* Local variables. */
|
|
int index_left, index_right, current_index;
|
|
|
|
/* Sanity check. */
|
|
if (array == NULL || value == NULL || comparison_function == NULL || size <= 0 || length <= 0)
|
|
return BINARY_SEARCH_INDEX_NOT_FOUND;
|
|
|
|
/* Input values are correct, commence the search. */
|
|
/* Set the initial index values. */
|
|
index_left = 0;
|
|
index_right = length - 1;
|
|
/* Loop and search. */
|
|
while (index_left <= index_right) {
|
|
/* Calculate the current index. */
|
|
current_index = (index_left + index_right) / 2;
|
|
/* Check if we've found the number. */
|
|
if (comparison_function(array + (current_index * size), value) == BINARY_SEARCH_COMPARISON_EQUAL_TO)
|
|
return current_index;
|
|
/* Check if smaller/larger and continue accordingly. */
|
|
if (comparison_function(array + (current_index * size), value) == BINARY_SEARCH_COMPARISON_LESS_THAN)
|
|
index_left = current_index + 1;
|
|
else
|
|
index_right = current_index - 1;
|
|
}
|
|
|
|
/* Search failed! */
|
|
return BINARY_SEARCH_INDEX_NOT_FOUND;
|
|
}
|