Linear Search

Linear Search, also known as sequential search, is one of the simplest searching algorithms in computer science. It is used to find the position of a particular element (target) in a list or array by checking each element one by one, from the beginning to the end.

How Linear Search Works?

Start from the first element of the array.
Compare the target element with the current element.
If a match is found, return the index.
If not, move to the next element.
Repeat until the end of the list.
If the target is not found, return -1 or indicate "not found."

Example of Linear Search

Let’s say we have the following array:

arr = [10, 25, 30, 45, 50]

And we want to search for the element 30.

Step 1:

Start from the first element of the array.

Check if arr[0] is equal to 30.

arr[0] = 10 → This is not equal to 30. So, move to the next element.

Step 2:

Check arr[1].

arr[1] = 25 → Still not equal to 30. Keep searching.

Step 3:

Check arr[2]

arr[2] = 30 → This matches the element we are looking for!

So, we stop the search here.

Final Result

The element 30 is found at index 2 in the array.

Time and Space Complexity of Linear Search

Time Complexity

Let n be the number of elements in the array.

Best Case	O(1) The target element is found at the first index.
Average Case	O(n) The target is somewhere in the middle.
Worst Case	O(n) The target is at the last index or not present at all.

In the worst case, the algorithm needs to check every element in the array.

Space Complexity

Linear search uses constant space O(1). It does not require any extra data structures or memory other than a few variables.

Why is Linear Search Less Efficient?

Linear search is simple, but not efficient for large datasets. It checks each element one by one, so as the number of elements increases, the time taken increases linearly.

If the data is sorted, more efficient algorithms like binary search (O(log n)) are preferred.

When to Use Linear Search

When the array is unsorted.
When the dataset is small.
When simplicity is more important than efficiency.

Advantages

Easy to implement and understand.
No need for sorted data.

Disadvantages

Inefficient for large datasets.
Time-consuming compared to more advanced searching techniques like binary search.

Example: Linear Search in 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;  // Element found
    }
    return -1;  // Element not found
}

int main() {
    int arr[] = {5, 3, 7, 2, 9, 1};
    int key = 2;
    int n = sizeof(arr) / sizeof(arr[0]);

    int result = linearSearch(arr, n, key);
    if (result != -1)
        printf("Element %d found at index %d.\n", key, result);
    else
        printf("Element %d not found in the array.\n", key);

    return 0;
}

Output

Element 2 found at index 3.

Menu