A linear search implementation for any data type in C

Question

I performed an "experiment" to test my understanding of pointers in C. I decided to write a linear search function that can work on any array provided there is an existing function to compare the elements of the array. Here are the files:

linear_search.h

#ifndef _LINEAR_SEARCH_H
#define _LINEAR_SEARCH_H

/*
 * Summary:
 *  Performs linear search on the given array using the given
 * comparator function. Returns the index of the matching array
 * element (< len), and -1 if the element is not found.
 *
 *  Parameters are independent of type and hence this function
 * can be used for arrays of all data-types, provided that the width
 * (i.e. size of the datatype in terms of bytes) is properly specified.
 *
 * Parameters:
 *  1. *base - the address of the array from whence we start searching.
 *  2. *x    - the address of the element to find in the array
 *  3. len   - the maximum number of elements we are willing to search against.
 *  4. width - the width of each element of the array (in bytes)
 *  5. compare(void*, void*)
 *           - the function which is used for comparison. Zero is taken to be equality.
 */
long long linear_search
    (
        const void *base, const void *x, const long long len, const int width,
        const int (*compare)(const void *, const void *)
    );

#endif

linear_search.c

long long linear_search
    (
        const void *base, const void *x, const long long len, const int width,
        const int (*compare)(const void *, const void *)
    )
{
    long long index = 0;
    // convert to a char * pointer in order to make the pointer arithmetic in terms of 1 byte
    char *base_ptr = (char *) base;
    for (; index < len; index++) {
        if ((*compare)((base_ptr + index * width), x) == 0)
            return index;
    }
    return -1;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "linear_search.h"

const int compare(const void *a, const void *b)
{
    double *p = (double *) a;
    double *q = (double *) b;
    return *p - *q;
}

int main(int argc, char const *argv[])
{
    double *a;
    double x;
    int width;
    long long int index, len, i;
    width = sizeof(double);

    printf("Enter how many elements : ");
    scanf("%lld", &len);

    a = malloc(len * width);
    if (a == NULL) {
        printf("Error while trying to allocate memory.\n");
        return EXIT_FAILURE;
    }

    printf("Enter elements one-by-one:\n");
    for (i = 0; i < len; i++) {
        printf("%d : ", (i + 1));
        scanf("%lf", (a + i));
    }

    printf("Enter the element to look for : ");
    scanf("%lf", &x);
    index = linear_search(a, &x, len, width, compare);

    printf("Index is %lld\n", index);
    return EXIT_SUCCESS;
}

I would like to know if there's a better way to accomplish this task, or if I'm making any gross errors. While it's true that my program compiled without any errors or warnings, I am never sure when it comes to C. Suggestions (however small) and critique is welcome.

Answer 1

I think you have chosen some of your types poorly. You write:

long long linear_search
    (
        const void *base, const void *x, const long long len, const int width,
        const int (*compare)(const void *, const void *)
    );

If you take a look at the definition of bsearch, you would do well to be inspired by that function. Obviously, someone thought about how it will work, and also there's the "principle of least surprise" to consider: why should two search functions have different argument types or return different results? Or even pass their arguments in different orders?

Let's change the parameter names, and compare:

long long linear_search(const void *ptr, const void *key, const long long count, const int size, const int (*comp)(const void*, const void*));
void*     bsearch      (const void *key, const void *ptr,       size_t    count,    size_t size,       int (*comp)(const void*, const void*));

Parameter Order

The search function puts the key first, then the details of the array to be searched. Why?

Because the key isn't related to anything else in the parameter list, and it's the "important" thing in the search expression: Find me a needle! In this haystack, of such and such size. Use this comparator.

I'd suggest you reorder your parameters to conform with this. Not only is it a more sensible arrangement, it keeps your search function consistent with the "standard" search function. That means less to learn, and less chance for a silly bug.

Parameter Names

base, x, len, width, compare

versus

key, ptr, count, size, comp

I actually prefer base to ptr, but len and width aren't super clear. count and size are better in that regard.

Parameter Types

Your parameters are pointers, an array size, and a memory size. You got void * correct as the base type of the pointers (const because no changes). The array size and memory size should be size_t.

The numeric parameters, and the compare-function return type, do not need to be declared const. Declaring them const is a promise not to change them - but they're function arguments (& a return value)! Who cares if you change them, it's not like you're going to give them back! Get rid of those const declarations, since they provide no value to the caller.

Return Type

The bsearch function returns a pointer, rather than an index. Why?

Because it just found a pointer, and it's easier and faster to return the result that it has, instead of doing any math to maintain both a pointer and an index, or doing math to convert from pointer to index.

Also, because the likely next operation for the user who calls a search function will be to use the result of the call, which will require computing a pointer.

If you choose not to use a pointer, you will need a signed integral type that is adequate to store any array index. That would be ptrdiff_t, since it is signed and can express any value of the form (&a[i] - a). So long long should be replaced, either by void * or by ptrdiff_t.

Note that the return type of bsearch is declared as void * rather than const void *. Why? Because the data being searched is probably not constant, and that's the "most compatible" type - you can assign it to pretty much anything with less required casting than other options (char *, const void *, etc.).

Answer 2

@Austin Hastings good review leaves only some corner issues to consider.

I advocate avoiding manual formatting - recommend to use automatic formatting. Life is too short for spending time formatting code.

long long linear_search
    (
        const void *base, const void *x, const long long len, const int width,
        const int (*compare)(const void *, const void *)

// vs

long long linear_search(const void *base, const void *x, const long long len,
    const int width, const int (*compare)(const void *, const void *))

---

Use size_t for size variables.

---

Your code can detect troublesome len,width combinations

assert(width == 0  || SIZE_MAX/width <= len);

Pedantic: Rare machines allow allocated memory more than SIZE_MAX via calloc(). Thus base_ptr + index * width may overflow. The solution relies on implementation dependent code.

---

A search of a 0-length array should be tolerated. I'd say your code does that.

---

The compare function is wrong for double. Values like 0.4 and 0.3 would return (int)(0.4 - 0.3) which is 0. (equal).

Avoid unnecessarily cast aways const-ness.

const int compare(const void *a, const void *b) {
  //double *p = (double *) a;
  //double *q = (double *) b;
  const double *p = (const double *) a;
  const double *q = (const double *) b;
  // return *p - *q;
  return (*p > *q) - (*p < *q);
}

---

Even better compare(). Consider above would compare 2 NaN as the same.

const int compare(const void *a, const void *b) {
  const double *p = (const double *) a;
  const double *q = (const double *) b;
  if (*p > *q) return 1;
  if (*p < *q) return -1;
  if (*p == *q) return 0;
  // at least one of the values NaN, customize as desired.
  // Recommended to consider it greater for `lsearch()` purposes.
  return TBD;
}

or simply

const int compare(const void *a, const void *b) {
  const double *p = (const double *) a;
  const double *q = (const double *) b;
  return !(*p == *q);  // note this is not the same as `*p != *q with NaN
}

---

Corner idea: bsearch() and your lsearch() do not specify in the compare(a,b) function, which of the arguments is the key. Yet with your lsearch(), you could specify one of the 2 such as compare(a,key). With this hint, the compare function may be able to optimize is some fashion knowing the key is second. Of course the compare() should be made to work in either direction.

A 2nd thought along this line: if the key is always the a (or b) of the compare function, the type or p, q need not be the same. Caveat emptor