C Linear Search

Linear search (also called sequential search) is the simplest way to find a value inside an array: you check each element one by one, in order, until you find the value you’re looking for or run out of elements. It doesn’t require the data to be sorted, which makes it the most flexible search algorithm, even though it isn’t the fastest for large datasets.

Every programmer should master linear search first because it builds the mental model for every other search algorithm you’ll learn later, including binary search. It also shows up constantly in real code: searching an unsorted list of records, scanning a small configuration array, or checking whether an item exists in a collection before inserting it.

Overview / How It Works

The idea behind linear search is straightforward: start at the first element of the array and compare it to the target value (the "key" you’re searching for). If it matches, you’re done — return that position. If it doesn’t match, move to the next element and repeat. If you reach the end of the array without finding a match, the value isn’t present.

Internally, an array in C is just a contiguous block of memory. When you write arr[i], the compiler computes the memory address as base_address + i * sizeof(element) and reads the value stored there. Linear search walks this memory block sequentially, using a loop counter i that increases by one on each iteration. Because the CPU reads memory in a predictable, forward-moving pattern, linear search also benefits from CPU cache locality — nearby array elements are often already loaded into the cache, which makes each comparison fast in practice, even though the algorithm itself is not asymptotically optimal.

Linear search makes no assumptions about the order of the data. That’s its biggest strength (it works on any array, sorted or not) and also the reason it’s slower than alternatives like binary search, which requires sorted data but can eliminate half the remaining elements with every comparison.

Time and Space Complexity

Case	Complexity	Meaning
Best case	O(1)	The target is the very first element
Average case	O(n)	The target is found roughly halfway through, on average
Worst case	O(n)	The target is the last element, or absent entirely
Space	O(1)	No extra memory is needed beyond the loop variables

Syntax

Linear search doesn’t have special C syntax — it’s a plain loop. The general pattern looks like this:

for (int i = 0; i < n; i++) {
    if (arr[i] == key) {
        // found at index i
        break;
    }
}

arr — the array being searched.
n — the number of elements in the array (C arrays don’t know their own length, so you must track it separately, usually with sizeof(arr) / sizeof(arr[0]) for a stack array, or a parameter you pass around).
key — the value you’re searching for.
i — the loop index, used both to walk the array and, if the match is found, to report the position.
break — stops the loop as soon as a match is found, avoiding wasted comparisons.

Examples

Example 1: Basic linear search in an integer array

#include <stdio.h>

int main(void) {
    int arr[] = {34, 12, 87, 45, 9, 63, 21};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 45;
    int found = -1;

    for (int i = 0; i < n; i++) {
        if (arr[i] == target) {
            found = i;
            break;
        }
    }

    if (found != -1) {
        printf("Value %d found at index %d\n", target, found);
    } else {
        printf("Value %d not found in array\n", target);
    }

    return 0;
}

Output:

Value 45 found at index 3

The loop compares arr[i] to target on each iteration. Since 45 sits at index 3 (after 34, 12, and 87), the loop stops there and found is set to 3. The break statement means the remaining elements (9, 63, 21) are never even examined.

Example 2: A reusable linearSearch function

In real programs you rarely inline the search loop — you wrap it in a function so it can be reused for different arrays and queries.

#include <stdio.h>

int linearSearch(const int arr[], int n, int key) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == key) {
            return i;
        }
    }
    return -1;
}

int main(void) {
    int scores[] = {88, 92, 76, 100, 65, 59, 81};
    int n = sizeof(scores) / sizeof(scores[0]);
    int queries[] = {100, 59, 40};
    int qn = sizeof(queries) / sizeof(queries[0]);

    for (int i = 0; i < qn; i++) {
        int idx = linearSearch(scores, n, queries[i]);
        if (idx == -1) {
            printf("%d not found\n", queries[i]);
        } else {
            printf("%d found at index %d\n", queries[i], idx);
        }
    }

    return 0;
}

Output:

100 found at index 3
59 found at index 5
40 not found

The function linearSearch takes the array, its length, and the key, and returns the index of the first match or -1 if nothing matches. Using a dedicated function means the same search logic works for the scores array here, or any other int array elsewhere in the program, without duplicating the loop.

Example 3: Searching an array of strings and counting matches

Linear search isn’t limited to numbers. You can search any array of comparable elements — including strings, provided you compare them correctly with strcmp instead of == (which would compare pointers, not contents).

#include <stdio.h>
#include <string.h>

int main(void) {
    const char *fruits[] = {"apple", "mango", "banana", "mango", "grape", "mango"};
    int n = sizeof(fruits) / sizeof(fruits[0]);
    const char *target = "mango";
    int count = 0;

    printf("Occurrences of \"%s\" at indices: ", target);
    for (int i = 0; i < n; i++) {
        if (strcmp(fruits[i], target) == 0) {
            printf("%d ", i);
            count++;
        }
    }
    printf("\nTotal occurrences: %d\n", count);

    return 0;
}

Output:

Occurrences of "mango" at indices: 1 3 5 
Total occurrences: 3

This example shows two useful variations on the basic pattern: comparing strings with strcmp (which returns 0 when two strings are equal), and continuing the loop after a match instead of breaking, so that every occurrence is found rather than just the first one.

How It Works Step by Step

Using Example 1 (searching for 45 in {34, 12, 87, 45, 9, 63, 21}), here is exactly what happens:

i = 0: Compare arr[0] (34) to 45. No match. Increment i.
i = 1: Compare arr[1] (12) to 45. No match. Increment i.
i = 2: Compare arr[2] (87) to 45. No match. Increment i.
i = 3: Compare arr[3] (45) to 45. Match! Store found = 3 and break out of the loop immediately.

Notice that the loop never reaches i = 4 through i = 6. This is the practical benefit of break: as soon as the answer is known, further work is wasted work, so the loop exits early. If the target were not in the array at all, the loop would run all the way through i = 6, the condition i < n would become false, and found would remain -1.

Common Mistakes

Mistake 1: Forgetting to break after finding a match

If you only need the first match but forget break (or an equivalent return), the loop keeps running and may overwrite your result with a later, incorrect index if the search isn’t written carefully — or simply waste time scanning elements that no longer matter.

// Wrong: keeps looping even after a match is found
for (int i = 0; i < n; i++) {
    if (arr[i] == target) {
        found = i;
    }
}

This particular version happens to still end up correct only if you want the last match, but if your intent was the first match, it silently gives you the wrong index whenever the value appears more than once. Fix it by exiting as soon as you find what you’re looking for:

// Correct: stop as soon as the first match is found
for (int i = 0; i < n; i++) {
    if (arr[i] == target) {
        found = i;
        break;
    }
}

Mistake 2: Comparing strings with == instead of strcmp

Beginners often try to search an array of C strings the same way they search numbers:

// Wrong: compares pointer addresses, not string contents
if (fruits[i] == target) {
    // almost never true, even when the text matches
}

Because fruits[i] and target are both char * pointers, == compares memory addresses, not the characters they point to. Two separate string literals with identical text can (and often do) live at different addresses, so the comparison silently fails even when the words are the same. Always use strcmp for string content comparison:

// Correct: compares the actual characters
if (strcmp(fruits[i], target) == 0) {
    // true when the text matches
}

Mistake 3: Using the wrong length for the array

The trick sizeof(arr) / sizeof(arr[0]) only works on the original array variable, not on a pointer. If you pass an array to a function, it decays into a pointer, and sizeof inside that function returns the pointer’s size (commonly 8 on 64-bit systems), not the array’s length — producing a wrong, much smaller loop bound. Always compute the length in the scope where the array is still a real array, and pass it as a separate parameter, as shown in Example 2.

Best Practices

Always pass the array length as a separate parameter to search functions — never rely on sizeof inside a function that receives an array as a parameter.
Use break or return as soon as a match is found if you only need the first occurrence; it avoids unnecessary comparisons and makes intent clear.
Return a sentinel value like -1 (for indices, which are always non-negative) to signal "not found," and always check for it before using the result.
Use strcmp (or strncmp) for comparing C strings, never ==, since == compares pointers, not text.
Mark array parameters const in search functions (e.g. const int arr[]) when the function doesn’t modify the array — this documents intent and lets the compiler catch accidental writes.
For large datasets that are searched repeatedly, consider sorting the data once and using binary search, or using a hash table, instead of linear search, since both offer far better average performance than O(n).
Linear search is still the right tool when the data is small, unsorted, only searched once, or stored in a data structure (like a linked list) that doesn’t support fast random access.

Practice Exercises

Exercise 1: Write a function int countOccurrences(const int arr[], int n, int key) that returns how many times key appears in arr, using linear search. Test it on {5, 3, 5, 5, 8, 2, 5} searching for 5 (expected result: 4).
Exercise 2: Modify the string-search example (Example 3) so it also prints "Not found" when the target fruit doesn’t appear at all, instead of printing an empty list of indices.
Exercise 3: Write a function that performs linear search on an array of float values and returns the index of the first value within 0.0001 of the target (since floating-point values should rarely be compared with exact equality). Test it by searching for 3.14 in an array that contains 3.14000001.

Summary

Linear search checks each array element in order until it finds a match or reaches the end of the array.
It works on both sorted and unsorted data, unlike binary search, which requires sorted data.
Time complexity is O(1) best case, O(n) average and worst case; space complexity is O(1).
Always track the array length separately in C, since arrays don’t carry their own size, especially across function calls where arrays decay to pointers.
Use strcmp to compare C strings by content, never ==, which compares pointer addresses.
Use break or return to stop the search as soon as the first needed match is found, unless you deliberately need every occurrence.
For large, frequently searched, sortable datasets, prefer binary search or a hash table over linear search.

C Linear Search

Overview / How It Works

Time and Space Complexity

Syntax

Examples

Example 1: Basic linear search in an integer array

Example 2: A reusable linearSearch function

Example 3: Searching an array of strings and counting matches

How It Works Step by Step

Common Mistakes

Mistake 1: Forgetting to break after finding a match

Mistake 2: Comparing strings with == instead of strcmp

Mistake 3: Using the wrong length for the array

Best Practices

Practice Exercises

Summary

Table of Contents