Linear Search in C: Programs, Algorithm and Complexity

Linear search in C checks array elements one at a time until it finds a target or reaches the end. It works on unsorted arrays. A first-match search returns the earliest matching index; an all-occurrences search keeps scanning for duplicates. The programs below show both policies, plus recursion, with complete source you can run online. They use small fixed arrays so you can focus on the search rather than input parsing.

Iterative linear search using a function

This example looks for 7 in {12, 7, 19, 7, 3}. C arrays use zero-based indices, so the first match is at index 1, which is position 2 if you count elements from 1. The function returns -1 when no match exists. Returning index 0 must not be confused with returning false.

#include <stdio.h>

int linear_search(const int values[], int count, int target) {
    for (int i = 0; i < count; ++i) {
        if (values[i] == target) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    int values[] = {12, 7, 19, 7, 3};
    int count = (int)(sizeof values / sizeof values[0]);
    int target = 7;
    int index = linear_search(values, count, target);

    if (index >= 0) {
        printf("First match: index %d (position %d)\n", index, index + 1);
    } else {
        puts("Not found");
    }
    return 0;
}

First match: index 1 (position 2)

The array parameter is const because searching does not modify elements. The count and returned index use int for this small teaching example. Only use a nonnegative count representable in int, with that many accessible elements; this interface is not intended for arrays larger than INT_MAX elements. For a zero count the function does not dereference the pointer. A nonzero count requires a valid array.

Change the target to 12 to test index 0, to 3 to test the last index, and to 99 to test the missing-value branch. The expected output displayed with the original code remains a reference for that original code, not a record of your edits.

Algorithm and dry run

1. Start at index 0.
2. If the index has reached the element count, return -1.
3. Compare the current element with the target.
4. If equal, return this index. Otherwise advance to the next index and repeat.

Start at i = 0
      |
      v
Is i < count? -- no --> not found (-1)
      | yes
      v
values[i] == target? -- yes --> return i
      | no
      v
i++; repeat the bounds check

The second 7 at index 3 is deliberately not visited by the first-match function. If the target were 99, all five elements would be checked before returning -1. The loop bound is i < count, not i <= count; index count is already outside the array.

Recursive linear search

Recursion expresses the same decision in function calls. There are two stopping cases: the range is exhausted, or the current element matches. Every unsuccessful call advances the index, so it eventually reaches a stopping case for a valid finite range.

#include <stdio.h>

int linear_search_recursive(const int values[], int count,
                            int target, int index) {
    if (index < 0 || index >= count) {
        return -1;
    }
    if (values[index] == target) {
        return index;
    }
    return linear_search_recursive(values, count, target, index + 1);
}

int main(void) {
    int values[] = {12, 7, 19, 7, 3};
    int count = (int)(sizeof values / sizeof values[0]);
    int index = linear_search_recursive(values, count, 7, 0);

    if (index >= 0) {
        printf("First match: index %d\n", index);
    } else {
        puts("Not found");
    }
    return 0;
}

First match: index 1

Start at index 0 to search the whole array and return its first match. The same nonnegative-count and valid-array requirements apply. This form makes the recursive idea visible, but the iterative version is normally simpler and avoids a potentially deep call chain. Do not assume that a C compiler will eliminate these calls: tail-call optimization is not guaranteed. For a large array, recursion can exhaust stack space.

Find every occurrence, including duplicates

To report all matches, do not return immediately on equality. Continue through the entire array and count how many indices matched. This function prints matches as it finds them and returns the count. In reusable library code, you might instead write matching indices into a caller-provided buffer with an explicit capacity.

#include <stdio.h>

int print_occurrences(const int values[], int count, int target) {
    int matches = 0;
    for (int i = 0; i < count; ++i) {
        if (values[i] == target) {
            printf("Found at index %d\n", i);
            ++matches;
        }
    }
    return matches;
}

int main(void) {
    int values[] = {12, 7, 19, 7, 3};
    int count = (int)(sizeof values / sizeof values[0]);
    int matches = print_occurrences(values, count, 7);
    printf("Total matches: %d\n", matches);
    return 0;
}

Found at index 1
Found at index 3
Total matches: 2

This version reports index 1 and index 3. For a missing value it prints no index lines, and main prints Total matches: 0. A zero-length call has the same result. The function still scans the whole array even if the first element matches, because later matches must not be missed.

Time and space complexity

For a successful first-match search with the target equally likely to be at each index, the average number of comparisons is (n + 1) / 2. That still grows linearly with n. This assumption is not a promise about every real dataset: a target that is usually at the front can be found much sooner. A missing target always needs the full scan in the ordinary unsorted case.

Linear search versus binary search

See the binary search program for the sorted-array algorithm. Do not apply it to the unsorted array on this page: it can incorrectly reject a value that is present. Sorting only to perform one search can cost more than a scan, and sorting changes positions unless original indices are preserved. For repeated searches, sorting once may be worthwhile. Insertion sort demonstrates how sorting changes the array; it is especially straightforward for small inputs.

Common mistakes and boundary tests

• Testing if (index) instead of index >= 0: index 0 is a valid match, while -1 is nonzero. Test the documented return convention.
• Returning “not found” inside the loop after one mismatch: the target may be later in the array. Return -1 only after the scan finishes.
• Reading past the end: use < count. A negative count is outside the documented interface, not an alternate array length.
• Confusing value and index: returning 7 is not correct merely because 7 is the target; the caller needs its location.
• Claiming all matches after stopping early: choose first-match or all-occurrences behavior explicitly.
• Losing array length in a function: pass the count separately. sizeof on an array parameter measures a pointer, not the original array.

Test a first-element match, a last-element match, a missing target, repeated values, negative values, one element, and zero elements. For standard C, a zero-element test uses a zero count, not a zero-length array declaration. Do not pass an invalid nonzero length just to simulate “not found”; that is an out-of-bounds memory access.

Practice questions

1. Trace target 19 in the displayed array. The result should be index 2 after three comparisons.
2. Change the array to {4, 4, 4}. The first-match function returns 0; the all-occurrences version reports three indices.
3. Adapt the iterative function to return the last match. Keep scanning and update a saved result instead of returning on equality.
4. Search an array of records by a chosen field. Define what equality means for that field before changing the algorithm.

Frequently asked questions

Can linear search handle an unsorted array?

Yes. It checks elements directly and makes no sorted-order assumption. That is its main practical difference from binary search.

Which version should a beginner use?

Start with the iterative function. It uses constant auxiliary space and makes the bounds check easy to see. Study the recursive version to understand base cases, not because recursion makes this particular search faster.

How do I compile these examples?

Each program is a separate complete file with its own main. Do not concatenate all three into one C file. Use its run link to load it in the online C compiler, or compile one file locally with gcc -std=c17 -Wall -Wextra -pedantic search.c -o search. If the arrangement of headers, functions and main is new, read the structure of a C program first.