Generic Linear Search – in C

Linear search is the simplest search algorithm – as simple as getting pulled over by the cops in front of a donut shop. One advantage of this algorithm is it uses simple data types and does not require the data to be sorted. It simply involves starting at the very beginning of an array and checking the value at each index against our key. This algorithm, however, is the slowest algorithm and is O(n). For randomly distributed data, the probability of finding the key would be n/2 (for large n).

See the post covering Why Linear Search is Order(n) for more information. The code below is made generic which means it will work on any data type that is in an array format (i.e., arrays of numbers and arrays of structures). It uses a function pointer as the last parameter. Hence, you simply generate your compare function for your data and pass the function name into the generic linear search function. Easy peasy right.

#include<stdlib.h>
/*
Generic Linear search

Return index value else -1 if not found
*/

int linearSearch(void *array, void *key, size_t length, size_t elementSize,
    int (*compare)(void *currentElement, void *key, size_t elementSize)){
    int i;

    for(i = 0; i < length; i++){
        void *currentElement=array+i*elementSize;
        if(compare(currentElement, key, elementSize))
            return i;
    }
    return -1;
}

Share: