Linear Search Algorithm in DSA C++

Mental Model

Look at each item one by one until you find the target or reach the end.

Analogy: Like searching for a book on a shelf by checking each book from left to right until you find the one you want.

Array: [3] -> [7] -> [1] -> [9] -> [5] -> null
Search target: 9
↑ Start at index 0

Dry Run Walkthrough

Input: array: [3, 7, 1, 9, 5], search for value 9

Goal: Find the index of value 9 in the array or report not found

Step 1: Check element at index 0

[3↑] -> [7] -> [1] -> [9] -> [5]

Why: Start from the first element to compare with target

Step 2: Check element at index 1

[3] -> [7↑] -> [1] -> [9] -> [5]

Why: First element not target, move to next

Step 3: Check element at index 2

[3] -> [7] -> [1↑] -> [9] -> [5]

Why: Still not target, continue searching

Step 4: Check element at index 3

[3] -> [7] -> [1] -> [9↑] -> [5]

Why: Found the target value at index 3

Result:

[3] -> [7] -> [1] -> [9↑] -> [5]
Answer: Found at index 3

Annotated Code

DSA C++

#include <iostream>
#include <vector>

int linearSearch(const std::vector<int>& arr, int target) {
    for (int i = 0; i < (int)arr.size(); i++) {
        if (arr[i] == target) {
            return i; // found target, return index
        }
    }
    return -1; // target not found
}

int main() {
    std::vector<int> arr = {3, 7, 1, 9, 5};
    int target = 9;
    int index = linearSearch(arr, target);
    if (index != -1) {
        std::cout << "Found at index " << index << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    return 0;
}

for (int i = 0; i < (int)arr.size(); i++) {

iterate over each element in the array

if (arr[i] == target) {

check if current element matches the target

return i; // found target, return index

stop search and return index when target found

return -1; // target not found

return -1 if target is not in the array

Output

Found at index 3

Complexity Analysis

Time: O(n) because in the worst case we check each element once

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to binary search which is O(log n), linear search is slower but works on unsorted arrays

Edge Cases

empty array

returns -1 immediately since no elements to check

DSA C++

for (int i = 0; i < (int)arr.size(); i++) {

target is first element

returns index 0 immediately after first check

DSA C++

if (arr[i] == target) {

target not in array

checks all elements and returns -1 at end

DSA C++

return -1; // target not found

When to Use This Pattern

When you need to find an item in a list without any order, use linear search because it checks each item one by one.

Common Mistakes

Mistake: Stopping the search too early without checking all elements
Fix: Only stop when the target is found or after checking all elements

Mistake: Returning index before confirming the element matches target
Fix: Always compare element with target before returning index

Summary

It looks through each element in order to find the target value.

Use it when the list is unsorted or small.

The key is checking each item one by one until you find the target or reach the end.