### 9.2 Array Search Function ¶

Generally searching for a specific element in an array means that potentially all elements must be checked. The GNU C Library contains functions to perform linear search. The prototypes for the following two functions can be found in `search.h`.

Function: `void *` lfind `(const void *key, const void *base, size_t *nmemb, size_t size, comparison_fn_t compar)` ¶

  Preliminary: | MT-Safe | AS-Safe | AC-Safe | See POSIX Safety Concepts.

  The `lfind` function searches in the array with `*nmemb` elements of size bytes pointed to by base for an element which matches the one pointed to by key. The function pointed to by compar is used to decide whether two elements match.

  The return value is a pointer to the matching element in the array starting at base if it is found. If no matching element is available `NULL` is returned.

  The mean runtime of this function is proportional to `*nmemb/2`, assuming random elements of the array are searched for. This function should be used only if elements often get added to or deleted from the array in which case it might not be useful to sort the array before searching.

Function: `void *` lsearch `(const void *key, void *base, size_t *nmemb, size_t size, comparison_fn_t compar)` ¶

  Preliminary: | MT-Safe | AS-Safe | AC-Safe | See POSIX Safety Concepts.

  The `lsearch` function is similar to the `lfind` function. It searches the given array for an element and returns it if found. The difference is that if no matching element is found the `lsearch` function adds the object pointed to by key (with a size of size bytes) at the end of the array and it increments the value of `*nmemb` to reflect this addition.

  This means for the caller that if it is not sure that the array contains the element one is searching for the memory allocated for the array starting at base must have room for at least size more bytes. If one is sure the element is in the array it is better to use `lfind` so having more room in the array is always necessary when calling `lsearch`.

To search a sorted or partially sorted array for an element matching the key, use the `bsearch` function. The prototype for this function is in the header file `stdlib.h`.

Function: `void *` bsearch `(const void *key, const void *array, size_t count, size_t size, comparison_fn_t compare)` ¶

  Preliminary: | MT-Safe | AS-Safe | AC-Safe | See POSIX Safety Concepts.

  The `bsearch` function searches array for an element that is equivalent to key. The array contains count elements, each of which is of size size bytes.

  The compare function is used to perform the comparison. This function is called with arguments that point to the key and to an array element, in that order, and should return an integer less than, equal to, or greater than zero corresponding to whether the key is considered less than, equal to, or greater than the array element. The function should not alter the array’s contents, and the same array element should always compare the same way with the key.

  Although the array need not be completely sorted, it should be partially sorted with respect to key. That is, the array should begin with elements that compare less than key, followed by elements that compare equal to key, and ending with elements that compare greater than key. Any or all of these element sequences can be empty.

  The return value is a pointer to a matching array element, or a null pointer if no match is found. If the array contains more than one element that matches, the one that is returned is unspecified.

  This function derives its name from the fact that it is implemented using the binary search algorithm.

  In ISO C23 and later, this function is qualifier-generic: that is, it is also implemented as a function-like macro, and when the macro is used and array has a type that is a pointer to a `const`-qualified object type, `bsearch` returns `const void *`. As an obsolescent feature, if the macro is suppressed the external function returns `void *` regardless.