Branch data Line data Source code
1 : : /* 2 : : * Copyright (c) 2019 Balaji Kulkarni 3 : : * 4 : : * SPDX-License-Identifier: Apache-2.0 5 : : */ 6 : : 7 : : #include <stdlib.h> 8 : : #include <stdio.h> 9 : : 10 : : /** 11 : : * @brief Generic implementation of Binary Search 12 : : * 13 : : * @param key pointer to first element to search 14 : : * @param array pointer to item being searched for 15 : : * @param count number of elements 16 : : * @param size size of each element 17 : : * @param cmp pointer to comparison function 18 : : * 19 : : * @return pointer to key if present in the array, or NULL otherwise 20 : : */ 21 : : 22 : : void *bsearch(const void *key, const void *array, size_t count, size_t size, 23 : : int (*cmp)(const void *key, const void *element)) 24 : : { 25 : 0 : size_t low = 0; 26 : 0 : size_t high = count; 27 : : size_t index; 28 : : int result; 29 : : const char *pivot; 30 : : 31 [ # # ]: 0 : while (low < high) { 32 : 0 : index = low + (high - low) / 2; 33 : 0 : pivot = (const char *)array + index * size; 34 : 0 : result = cmp(key, pivot); 35 : : 36 [ # # ]: 0 : if (result == 0) { 37 : 0 : return (void *)pivot; 38 [ # # ]: 0 : } else if (result > 0) { 39 : 0 : low = index + 1; 40 : : } else { 41 : 0 : high = index; 42 : : 43 : : } 44 : : } 45 : 0 : return NULL; 46 : : }