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: Like searching for a book on a shelf by checking each book from left to right until you find it.

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

Dry Run Walkthrough

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

Goal: Find the position of value 1 in the array or say not found

Step 1: Check element at index 0

[5] -> [3] -> [7] -> [1] -> [9] -> null
↑ at index 0 (value 5)

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

Step 2: Move to element at index 1

[5] -> [3] -> [7] -> [1] -> [9] -> null
    ↑ at index 1 (value 3)

Why: Value 5 is not 1, so check next element

Step 3: Move to element at index 2

[5] -> [3] -> [7] -> [1] -> [9] -> null
        ↑ at index 2 (value 7)

Why: Value 3 is not 1, continue searching

Step 4: Move to element at index 3

[5] -> [3] -> [7] -> [1] -> [9] -> null
            ↑ at index 3 (value 1)

Why: Found the value 1 at index 3

Result:

Final state: [5] -> [3] -> [7] -> [1] -> [9] -> null
Found value 1 at index 3

Annotated Code

DSA C#

using System;

class LinearSearch {
    public static int Search(int[] arr, int target) {
        for (int i = 0; i < arr.Length; i++) {
            if (arr[i] == target) {
                return i; // found target at index i
            }
        }
        return -1; // target not found
    }

    static void Main() {
        int[] array = {5, 3, 7, 1, 9};
        int target = 1;
        int result = Search(array, target);
        if (result != -1) {
            Console.WriteLine($"Found value {target} at index {result}");
        } else {
            Console.WriteLine($"Value {target} not found in array");
        }
    }
}

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

iterate over each element in the array

if (arr[i] == target) {

check if current element matches the target value

return i; // found target at index i

stop and return index when target is found

return -1; // target not found

return -1 if target is not in the array

Output

Found value 1 at index 3

Complexity Analysis

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

Space: O(1) because we only use 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 because there are no elements to check

DSA C#

for (int i = 0; i < arr.Length; 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 the 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: Make sure to only stop when the target is found or after checking all elements

Mistake: Returning index before checking the element
Fix: Check if the element matches the target before returning the index

Summary

It looks through each item in a list one by one to find a target value.

Use it when the list is unsorted or small and you need a simple search.

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

Practice

1. What does the linear search algorithm do when searching for a value in a list?

easy

A. It checks each element one by one until it finds the value or reaches the end.

B. It divides the list into halves to find the value quickly.

C. It sorts the list before searching for the value.

D. It uses a hash table to find the value 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:

   It checks each element one by one until it finds the value or reaches the end. -> 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 sorts the list first
• Assuming linear search uses extra data structures

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

easy

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

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

C. foreach (int i in arr.Length)

D. while (i < arr.Length) i++"

Solution

1. Step 1: Identify correct for loop syntax for arrays

   In C#, arrays use zero-based indexing, so loop starts at 0 and runs while i < arr.Length.

2. Step 2: Check each option

   for (int i = 0; i < arr.Length; i++) uses correct syntax: for (int i = 0; i < arr.Length; i++). Others have errors like starting at 1 or wrong foreach syntax.

3. Final Answer:

   for (int i = 0; i < arr.Length; i++) -> Option A

4. Quick Check:

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

Hint: Array loops start at 0 and go to Length-1 [OK]

Common Mistakes:

• Starting loop at 1 instead of 0
• Using <= instead of < in loop condition
• Incorrect foreach syntax for arrays

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

int[] arr = {4, 7, 1, 3, 9};
int target = 3;
int index = -1;
for (int i = 0; i < arr.Length; i++) {
  if (arr[i] == target) {
    index = i;
    break;
  }
}
Console.WriteLine(index);

medium

A. 4

B. 1

C. -1

D. 3

Solution

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

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

2. Step 2: Print the index found

   After loop, index = 3, so Console.WriteLine prints 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Target 3 found at index 3 [OK]

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

Common Mistakes:

• Forgetting to break loop after finding target
• Printing value instead of index
• Confusing index with element value

4. The following code is intended to perform a linear search but has a bug. What is the bug?

int[] arr = {2, 5, 8, 12};
int target = 8;
int index = -1;
for (int i = 0; i <= arr.Length; i++) {
  if (arr[i] == target) {
    index = i;
    break;
  }
}
Console.WriteLine(index);

medium

A. The index variable should be initialized to 0.

B. The target value is not in the array.

C. The loop condition should be i < arr.Length, not i <= arr.Length.

D. The break statement is missing.

Solution

1. Step 1: Analyze loop condition

   The loop runs while i <= arr.Length, but valid indices are 0 to arr.Length - 1. Using <= causes out-of-range error.

2. Step 2: Correct the loop condition

   Change condition to i < arr.Length to avoid accessing invalid index.

3. Final Answer:

   The loop condition should be i < arr.Length, not i <= arr.Length. -> Option C

4. Quick Check:

   Loop condition must be less than Length [OK]

Hint: Use i < arr.Length to avoid index errors [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Assuming target not found is a bug
• Changing index initialization unnecessarily

5. You have an array int[] arr = {5, 3, 7, 3, 9}. You want to find the index of the second occurrence of the value 3 using linear search. Which approach is correct?

hard

A. Sort the array first, then find the value 3.

B. Use a counter to track occurrences and return index when counter reaches 2.

C. Return the first index where value 3 is found.

D. Use binary search to find the second occurrence.

Solution

1. Step 1: Understand the problem of finding second occurrence

   Linear search must count how many times target appears and return index at second time.

2. Step 2: Evaluate options

   Sort the array first, then find the value 3. sorts the array, changing indices. Return the first index where value 3 is found. returns only the first occurrence. Use binary search to find the second occurrence. uses binary search, unsuitable for unsorted array and specific occurrences. Use a counter to track occurrences and return index when counter reaches 2. correctly uses a counter to track occurrences and return the index of the second match.

3. Final Answer:

   Use a counter to track occurrences and return index when counter reaches 2. -> Option B

4. Quick Check:

   Count occurrences to find second index [OK]

Hint: Count matches, return index at second match [OK]

Common Mistakes:

• Returning first occurrence instead of second
• Sorting array which changes original order
• Using binary search on unsorted array