Linear Search in C – Sequential Search with Step-by-Step Trace

Linear search (also called sequential search) is the simplest searching algorithm: start at the first element, compare each element to the key, and stop when you find a match or exhaust the array. It makes no assumption about the data being sorted. It runs in O(n) time and O(1) space — no extra memory needed beyond a loop counter.

The original post used conio.h, void main(), and printed “search is successfull” (typo included). The search logic was correct but the code wouldn’t compile under standard GCC. This rewrite extracts the search into a named function and handles both integers and the not-found case cleanly.

C Program: Linear Search

/* Linear search: find a key in an unsorted array
 * Returns the first index where key is found, or -1 if not found
 * Compile: gcc -ansi -Wall -Wextra linearsearch.c -o linearsearch */
#include <stdio.h>

#define MAX 100

int linear_search(int a[], int n, int key)
{
    int i;
    for (i = 0; i < n; i++)
        if (a[i] == key)
            return i;   /* found: return 0-based index */
    return -1;          /* not found */
}

int main(void)
{
    int a[MAX], n, i, key, pos;

    printf("Enter number of elements (max %d): ", MAX);
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX) {
        printf("Invalid.\n");
        return 1;
    }

    printf("Enter %d integers:\n", n);
    for (i = 0; i < n; i++)
        if (scanf("%d", &a[i]) != 1) { printf("Invalid.\n"); return 1; }

    printf("Enter key to search: ");
    if (scanf("%d", &key) != 1) { printf("Invalid.\n"); return 1; }

    pos = linear_search(a, n, key);

    if (pos >= 0)
        printf("Key %d found at index %d (1-based position: %d)\n",
               key, pos, pos + 1);
    else
        printf("Key %d not found in the array.\n", key);

    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra linearsearch.c -o linearsearch
./linearsearch

Sample Output

Enter number of elements (max 100): 8
Enter 8 integers:
3 1 4 1 5 9 2 6
Enter key to search: 9
Key 9 found at index 5 (1-based position: 6)

Enter number of elements (max 100): 8
Enter 8 integers:
3 1 4 1 5 9 2 6
Enter key to search: 7
Key 7 not found in the array.

Step-by-Step Trace — key=9 in [3,1,4,1,5,9,2,6]

i	a[i]	a[i] == 9?	Action
0	3	No	continue
1	1	No	continue
2	4	No	continue
3	1	No	continue
4	5	No	continue
5	9	Yes	return 5

Code Explanation

Return -1 for not found — using -1 as a sentinel for “not found” is idiomatic in C. The function returns a valid array index (0 to n−1) on success, or -1 on failure. The caller checks if (pos >= 0) to distinguish the two cases. This is the same convention used by strcspn(), strstr(), and many standard library functions.
Returns the first match — if the key appears multiple times (like 1 in [3,1,4,1,5]), the function returns the index of the first occurrence. To find all occurrences, call the function multiple times with a start index parameter, or use a loop that continues after finding each match.
Works on unsorted data — unlike binary search, which requires the array to be sorted, linear search works on any array in any order. This is its key advantage: it handles dynamic data that changes frequently, where keeping a sorted order would be expensive.
Separate function — extracting linear_search() into its own function makes it reusable, testable independently of main, and clearly expresses its contract: given an array, size, and key, return an index or -1.

Linear Search vs Binary Search

Property	Linear Search	Binary Search
Requires sorted array	No	Yes
Time complexity	O(n)	O(log n)
Space complexity	O(1)	O(1) iterative
Best for	Small arrays, unsorted data	Large sorted arrays
n=1,000 (worst case)	1,000 comparisons	10 comparisons
n=1,000,000 (worst case)	1,000,000 comparisons	20 comparisons

What This Program Teaches

O(n) vs O(log n) search — linear search checks every element; binary search halves the search space each step. For 1 million elements, linear search takes up to 1 million comparisons; binary search takes at most 20. The tradeoff: binary search requires sorted data.
When to use linear search — small arrays (under ~50 elements, where overhead of sorting isn’t worth it), linked lists (no random access), data that changes frequently, or when you need to find the first match in an unsorted sequence.
Function return value conventions in C — returning a special value (-1, NULL, 0) to signal failure is the standard C pattern. Callers must always check for this sentinel. Never assume a search succeeded without checking the return value.

Related Programs

Practice what you learned: C Aptitude Questions — or try our C Programming Quiz App on Android.

C Program To Demonstrate Linear search