C Program for Linear Search with Example and Explanation

A C program for linear search uses a for loop to check each element in an array one by one until it finds the target value or reaches the end; example code: for(int i=0; i.

Examples

InputArray: [5, 3, 8, 6, 2], Key: 8

OutputElement found at index 2

InputArray: [1, 2, 3, 4, 5], Key: 10

OutputElement not found

InputArray: [7], Key: 7

OutputElement found at index 0

How to Think About It

To find a number in a list, start from the first item and check each one in order. If the number matches the one you want, stop and say where it is. If you reach the end without finding it, say it is not there.

Algorithm

1

Get the array and the number to find (key).

2

Start from the first element and check each element one by one.

3

If the current element equals the key, return its index.

4

If you reach the end without a match, return -1 to show not found.

Code

c

#include <stdio.h>

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

int main() {
    int arr[] = {5, 3, 8, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 8;
    int result = linearSearch(arr, n, key);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");
    return 0;
}

Output

Element found at index 2

Dry Run

Let's trace searching for 8 in the array [5, 3, 8, 6, 2].

1

Check index 0

arr[0] = 5, key = 8, not equal, continue

2

Check index 1

arr[1] = 3, key = 8, not equal, continue

3

Check index 2

arr[2] = 8, key = 8, equal, return index 2

Index	Array Value	Key	Match?
0	5	8	No
1	3	8	No
2	8	8	Yes

Why This Works

Step 1: Loop through array

The for loop goes through each element one by one to check for the key.

Step 2: Compare each element

Inside the loop, each element is compared with the key using ==.

Step 3: Return index if found

If a match is found, the function returns the current index immediately.

Step 4: Return -1 if not found

If the loop finishes without finding the key, the function returns -1 to indicate failure.

Alternative Approaches

Recursive Linear Search

c

#include <stdio.h>

int recursiveSearch(int arr[], int n, int key) {
    if (n == 0) return -1;
    if (arr[n-1] == key) return n-1;
    return recursiveSearch(arr, n-1, key);
}

int main() {
    int arr[] = {5, 3, 8, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 8;
    int result = recursiveSearch(arr, n, key);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");
    return 0;
}

Uses recursion instead of a loop; easier to understand for some but uses more memory due to function calls.

Sentinel Linear Search

c

#include <stdio.h>

int sentinelSearch(int arr[], int n, int key) {
    int last = arr[n-1];
    arr[n-1] = key;
    int i = 0;
    while (arr[i] != key) i++;
    arr[n-1] = last;
    if (i < n-1 || arr[n-1] == key) return i;
    return -1;
}

int main() {
    int arr[] = {5, 3, 8, 6, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 8;
    int result = sentinelSearch(arr, n, key);
    if (result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");
    return 0;
}

Uses a sentinel to reduce the number of comparisons inside the loop; slightly faster but modifies the array temporarily.

Complexity: O(n) time, O(1) space

Time Complexity

The program checks each element once in the worst case, so time grows linearly with array size.

Space Complexity

Only a few variables are used, so space stays constant regardless of input size.

Which Approach is Fastest?

Iterative linear search is simple and fast for small arrays; sentinel search can be faster but modifies data; recursive uses more memory.

Approach	Time	Space	Best For
Iterative Linear Search	O(n)	O(1)	Simple and safe for all arrays
Recursive Linear Search	O(n)	O(n)	When recursion is preferred, small arrays
Sentinel Linear Search	O(n)	O(1)	Slightly faster, when modifying array temporarily is okay