Linear Search Algorithm in DSA C

Mental Model

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

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

Array: [3] -> [7] -> [1] -> [9] -> [5] -> null
Index:  0      1      2      3      4
Search for: 9 ↑

Dry Run Walkthrough

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

Goal: Find the index of value 9 in the array or say it is not found

Step 1: Check element at index 0

[3] -> [7] -> [1] -> [9] -> [5] -> null
Index:  0↑     1      2      3      4

Why: Start from the first element to see if it matches the search value

Step 2: Check element at index 1

[3] -> [7] -> [1] -> [9] -> [5] -> null
Index:  0      1↑     2      3      4

Why: First element was not 9, so move to next element

Step 3: Check element at index 2

[3] -> [7] -> [1] -> [9] -> [5] -> null
Index:  0      1      2↑     3      4

Why: Keep checking each element in order

Step 4: Check element at index 3

[3] -> [7] -> [1] -> [9] -> [5] -> null
Index:  0      1      2      3↑     4

Why: Found the element 9 which matches the search value

Result:

Final state: [3] -> [7] -> [1] -> [9] -> [5] -> null
Index:  0      1      2      3↑     4
Answer: Found 9 at index 3

Annotated Code

DSA C

#include <stdio.h>

int linear_search(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // found target at index i
        }
    }
    return -1; // target not found
}

int main() {
    int arr[] = {3, 7, 1, 9, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
    int result = linear_search(arr, size, target);
    if (result != -1) {
        printf("Found %d at index %d\n", target, result);
    } else {
        printf("%d not found in the array\n", target);
    }
    return 0;
}

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

iterate through each element in the array

if (arr[i] == target) {

check if current element matches the target

return i; // found target at index i

return index immediately when target is found

return -1; // target not found

return -1 if target is not found after checking all elements

Output

Found 9 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 there are no elements to check

DSA C

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

target not in array

checks all elements and returns -1 at the end

DSA C

return -1; // target not found

target is the first element

returns index 0 immediately without checking further

DSA C

if (arr[i] == target) {

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: Make sure to only stop when the target is found or all elements are checked

Mistake: Returning the wrong index or value
Fix: Return the current index i when the target is found

Summary

Linear search looks at each element one by one to find a target value.

Use it when the list is unsorted or small.

The key is to check every element until you find the target or reach the end.

Practice

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

easy

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

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

C. Sort the list first then search using binary method

D. Use a hash table to find the target instantly

Solution

1. Step 1: Understand linear search process

   Linear search checks each element in order from start to end.

2. Step 2: Compare with other search methods

   Other methods like binary search divide the list, but linear search does not.

3. Final Answer:

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

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 list
• Assuming instant search with hash tables

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 = 0; i <= n; i++)

C. for (int i = 1; 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 for size n.

2. Step 2: Choose correct loop condition

   The loop should run from 0 to less than n, so i < n is correct.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Using <= n causes out-of-bounds access
• Starting loop at 1 misses first element
• Confusing array size with last index

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;
  }
}
printf("%d", index);

medium

A. 3

B. 2

C. -1

D. 7

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), stop loop.

2. Step 2: Identify index where target found

   Target 7 found at index 2, so index = 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Target 7 at arr[2] = 2 [OK]

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

Common Mistakes:

• Printing value instead of index
• Not breaking loop and printing last index
• Confusing index with element value

4. Find the error in this linear search code snippet in C:

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

medium

A. The array parameter should be a pointer, not an array

B. The function should return the element, not the index

C. The return -1 should be inside the loop

D. Loop starts at 1 and goes to <= n, causing out-of-bounds access

Solution

1. Step 1: Check loop indexing for array access

   Array indices in C start at 0 and go to n-1, but loop starts at 1 and goes to n, causing out-of-bounds at arr[n].

2. Step 2: Identify correct loop bounds

   Loop should start at 0 and run while i < n to avoid invalid access.

3. Final Answer:

   Loop starts at 1 and goes to <= n, causing out-of-bounds access -> Option D

4. Quick Check:

   Array index out-of-bounds due to wrong loop limits [OK]

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

Common Mistakes:

• Starting loop at 1 instead of 0
• Using <= n instead of < n in loop condition
• Returning element instead of index

5. You have an unsorted array arr with 10 elements where some elements repeat. You want to find the first occurrence index of the number 5 using linear search. Which approach is best to handle duplicates and return the correct index?

hard

A. Sort the array first, then use binary search to find 5

B. Traverse entire array, count all 5s, then return last index of 5

C. Traverse from start to end, return index immediately when 5 is found

D. Use a hash map to store counts, then find index of 5

Solution

1. Step 1: Understand requirement for first occurrence

   We want the first index where 5 appears, so searching from start is needed.

2. Step 2: Choose approach that stops at first match

   Linear search that returns immediately on first 5 found gives correct first occurrence index.

3. Final Answer:

   Traverse from start to end, return index immediately when 5 is found -> Option C

4. Quick Check:

   Stop at first match to get first occurrence [OK]

Hint: Return index immediately on first match [OK]

Common Mistakes:

• Counting all occurrences then returning last index
• Sorting changes original order, losing first occurrence
• Using hash map adds unnecessary complexity