Linear Search in Data Structures and Algorithms (DSA)

Searching is one of the most fundamental operations in computer science. Whether you’re looking up a contact in your phone, checking if a product exists in a store’s database, or verifying a password in a login system — search algorithms play a vital role.

One of the simplest and most straightforward searching techniques is Linear Search.

📌 What is Linear Search?

Linear Search (also called sequential search) is a brute-force searching algorithm that checks each element in the list one by one until it finds the target element or reaches the end of the list.

Think of it like flipping through a book page by page until you find the word you’re looking for.

⚙️ How Does Linear Search Work?

1. Start from the first element of the array/list.
2. Compare the current element with the target (key).
3. If the element matches, return the index (or say “found”).
4. If not, move to the next element.
5. Repeat until the element is found or the list ends.

If the target is not present in the array, the algorithm returns -1 (not found).

📝 Example

Suppose we have an array:

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

Steps:

• Compare 10 with 30 → not equal
• Compare 25 with 30 → not equal
• Compare 30 with 30 → ✅ Found at index 2

💻 Linear Search Algorithm (Pseudocode)

LinearSearch(arr, n, key):
    for i from 0 to n-1:
        if arr[i] == key:
            return i
    return -1

💻 Linear Search Implementation in PHP

<?php
function linearSearch($arr, $target) {
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        if ($arr[$i] == $target) {
            return $i; // Found, return index
        }
    }
    return -1; // Not found
}

// Example
$arr = [10, 25, 30, 45, 50];
$target = 30;

$result = linearSearch($arr, $target);

if ($result != -1) {
    echo "Element $target found at index $result";
} else {
    echo "Element $target not found in array";
}
?>

Output:

Element 30 found at index 2

⏱️ Time Complexity Analysis

• Best Case (O(1)) → When the element is the first item.
• Worst Case (O(n)) → When the element is at the end or not present at all.
• Average Case (O(n)) → On average, half of the list is scanned.

💾 Space Complexity

• O(1) → Linear search uses no extra space apart from a few variables.

✅ Advantages of Linear Search

• Very simple to implement.
• Works on both sorted and unsorted data.
• Useful for small datasets.

❌ Disadvantages of Linear Search

• Inefficient for large datasets.
• On average, takes O(n) time to find an element.
• Not suitable when data is sorted and faster algorithms (like Binary Search) can be used.

📊 Real-Life Analogy

Imagine you want to find a friend’s name in a guest list of 200 people. If the list is not sorted alphabetically, the only way is to start from the top and check each name — this is linear search in action.

🔄 When to Use Linear Search?

• When the dataset is small.
• When the data is unsorted.
• When simplicity is preferred over performance.