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.

Practice

1. What is the main idea behind the Linear Search Algorithm?

easy

A. Use a hash table to find the target instantly

B. Check each element one by one until the target is found or list ends

C. Sort the list first and then search using binary steps

D. Divide the list into halves repeatedly to find the target

Solution

1. Step 1: Understand linear search process

   Linear search checks each element in order, starting from the first, to find the target.

2. Step 2: Compare with other search methods

   Other methods like binary search divide the list, but linear search simply checks one by one.

3. Final Answer:

   Check each element one by one until the target is found or list ends -> Option B

4. Quick Check:

   Linear search = check elements one by one [OK]

Hint: Linear search checks elements one by one [OK]

Common Mistakes:

• Confusing linear search with binary search
• Thinking linear search requires sorted data
• Assuming linear search is faster than binary search always

2. Which of the following is the correct syntax to start a linear search loop in C++ for an array arr of size n?

easy

A. for (int i = 0; i <= n; i++)

B. for (int i = 1; i <= n; i++)

C. for (int i = 0; i < n; i++)

D. for (int i = 1; i < n; i++)

Solution

1. Step 1: Understand array indexing in C++

   Arrays in C++ start at index 0 and go up to n-1, so loop should run from 0 to less than n.

2. Step 2: Check loop conditions

   Loop with i < n ensures last index accessed is n-1, which is valid.

3. Final Answer:

   for (int i = 0; i < n; i++) -> Option C

4. Quick Check:

   Loop from 0 to n-1 = for (int i = 0; i < n; i++) [OK]

Hint: Array index starts at 0, loop till i < n [OK]

Common Mistakes:

• Using <= n causes out-of-bound access
• Starting loop at 1 misses first element
• Using wrong loop condition causing runtime errors

3. What will be the output of the following C++ code?

int arr[] = {4, 2, 7, 1, 9};
int n = 5;
int target = 7;
int index = -1;
for (int i = 0; i < n; i++) {
  if (arr[i] == target) {
    index = i;
    break;
  }
}
std::cout << index;

medium

A. 2

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace the loop to find target 7

   Check elements: arr[0]=4 (no), arr[1]=2 (no), arr[2]=7 (yes), so index = 2 and break.

2. Step 2: Output the index

   After break, index is 2, so output is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Target found at index 2 [OK]

Hint: Stop loop when target found, print index [OK]

Common Mistakes:

• Forgetting to break loop after finding target
• Printing target value instead of index
• Confusing index with position (1-based)

4. Identify the error in the following linear search code snippet:

int arr[] = {5, 3, 8, 6};
int n = 4;
int target = 6;
int index = -1;
for (int i = 1; i <= n; i++) {
  if (arr[i] == target) {
    index = i;
    break;
  }
}
std::cout << index;

medium

A. Both A and B are errors

B. Loop condition should be i < n, not i <= n

C. Loop starts at 1 instead of 0, missing first element

D. No error, code works fine

Solution

1. Step 1: Check loop start index

   Loop starts at 1, so arr[0] is never checked, missing first element.

2. Step 2: Check loop end condition

   Loop runs while i <= n, so i can be 4, but arr[4] is out of bounds (valid indices 0-3).

3. Final Answer:

   Both A and B are errors -> Option A

4. Quick Check:

   Loop must start at 0 and run i < n [OK]

Hint: Loop from 0 to less than n to avoid errors [OK]

Common Mistakes:

• Starting loop at 1 misses first element
• Using <= n causes out-of-bound access
• Ignoring array index limits

5. You have an unsorted array arr = {3, 5, 2, 9, 5, 2}. You want to find the first occurrence index of the number 5 using linear search. What will be the output and why?

medium

A. Error, because array has duplicates

B. 4, because linear search returns the last matching index

C. -1, because 5 is not found

D. 1, because linear search returns the first matching index

Solution

1. Step 1: Understand linear search behavior with duplicates

   Linear search returns the first index where target is found, ignoring later duplicates.

2. Step 2: Find first occurrence of 5 in array

   arr[0]=3 (no), arr[1]=5 (yes), so index = 1 is returned immediately.

3. Final Answer:

   1, because linear search returns the first matching index -> Option D

4. Quick Check:

   First occurrence index = 1 [OK]

Hint: Linear search stops at first match, returns its index [OK]

Common Mistakes:

• Returning last occurrence instead of first
• Assuming duplicates cause errors
• Returning -1 incorrectly when target exists