GNU Info

(libc.info)Array Search Function

---

Next: Array Sort Function Prev: Comparison Functions Up: Searching and Sorting

---

Enter node , (file) or (file)node

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, void *BASE, size_t *NMEMB,
          size_t SIZE, comparison_fn_t COMPAR)
     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
     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 `*NMEMB'/2.  This function
     should only be used 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)
     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 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)
     The `bsearch' function searches the sorted array ARRAY for an
     object 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 two pointer arguments and should return an
     integer less than, equal to, or greater than zero corresponding to
     whether its first argument is considered less than, equal to, or
     greater than its second argument.  The elements of the ARRAY must
     already be sorted in ascending order according to this comparison
     function.

     The return value is a pointer to the 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.