Linear Search Algorithm in DSA Python

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 friend in a line of people by checking each person from start to end until you find them.

Index: 0   1   2   3   4
Array: [5] -> [3] -> [7] -> [1] -> [9]
          ↑
        current position

Dry Run Walkthrough

Input: list: 5 -> 3 -> 7 -> 1 -> 9, search value: 7

Goal: Find the position of value 7 in the list or say it is not found

Step 1: Check element at index 0

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

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

Step 2: Check element at index 1

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

Why: First element was not 7, move to next element

Step 3: Check element at index 2 and find match

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

Why: Found the search value 7 at index 2, stop searching

Result:

5 -> 3 -> [7] -> 1 -> 9
Found value 7 at index 2

Annotated Code

DSA Python

def linear_search(arr, target):
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1

# Driver code
arr = [5, 3, 7, 1, 9]
target = 7
result = linear_search(arr, target)
if result != -1:
    print(f"Found value {target} at index {result}")
else:
    print(f"Value {target} not found in the list")

for index, value in enumerate(arr):

iterate over each element with its index to check all items

if value == target:

compare current element with the target value

return index

stop and return the index when target is found

return -1

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

Output

Found value 7 at index 2

Complexity Analysis

Time: O(n) because in the worst case we check every 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 lists

Edge Cases

empty list

returns -1 immediately because there are no elements to check

DSA Python

return -1

target not in list

checks all elements and returns -1 after finishing

DSA Python

return -1

target is the first element

returns index 0 immediately without checking further

DSA Python

return index

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 every element

Mistake: Returning the value instead of the index
Fix: Return the index to show the position of the found element

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 is the main idea behind the Linear Search Algorithm?

easy

A. Sort the list first then search using binary steps

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

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

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, one by one.

2. Step 2: Compare with other search methods

   Binary search divides list, hash uses extra memory, linear is simple sequential check.

3. Final Answer:

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

4. Quick Check:

   Linear search = sequential check [OK]

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

Common Mistakes:

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

2. Which of the following is the correct syntax to start a linear search loop over a list arr in Python?

easy

A. for i to len(arr):

B. for i in range(arr):

C. for i in arr:

D. for i in range(len(arr)):

Solution

1. Step 1: Identify how to loop over indices

   To access elements by index, use range(len(arr)).

2. Step 2: Check each option's correctness

   for i in arr: loops over elements, not indices; B is invalid because range needs an integer; D is invalid syntax.

3. Final Answer:

   for i in range(len(arr)): -> Option D

4. Quick Check:

   Loop indices = range(len(arr)) [OK]

Hint: Use range(len(arr)) to loop indices [OK]

Common Mistakes:

• Using range(arr) instead of range(len(arr))
• Trying to loop with invalid syntax like 'for i to len(arr)'
• Confusing looping over elements vs indices

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

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

print(linear_search([4, 2, 7, 1, 3], 7))

medium

A. 2

B. 3

C. -1

D. 7

Solution

1. Step 1: Trace the loop and compare elements

   Check elements: arr[0]=4 (no), arr[1]=2 (no), arr[2]=7 (yes, matches target 7).

2. Step 2: Return index when found

   Function returns index 2 immediately when target found.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Index of 7 in list = 2 [OK]

Hint: Return index when target matches during loop [OK]

Common Mistakes:

• Returning element value instead of index
• Returning -1 even when target is present
• Confusing index with element value

4. Find the error in this linear search function:

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] = target:
            return i
    return -1

medium

A. Using '=' instead of '==' in the if condition

B. Missing colon ':' after for loop

C. Returning -1 instead of None when not found

D. Looping over range(len(arr)) instead of arr

Solution

1. Step 1: Identify syntax error in condition

   The if condition uses '=' which is assignment, not comparison.

2. Step 2: Correct operator for comparison

   Use '==' to compare values in if condition.

3. Final Answer:

   Using '=' instead of '==' in the if condition -> Option A

4. Quick Check:

   Comparison needs '==' not '=' [OK]

Hint: Use '==' for comparison, '=' is assignment [OK]

Common Mistakes:

• Using single '=' in if condition
• Confusing assignment and comparison operators
• Ignoring syntax errors causing runtime failure

5. You want to find all positions of a target number in a list using linear search. Which modification to the code below will achieve this?

def linear_search_all(arr, target):
    positions = []
    for i in range(len(arr)):
        if arr[i] == target:
            # What to do here?
    return positions

print(linear_search_all([1, 3, 7, 3, 9, 3], 3))

hard

A. Return i immediately when target is found

B. Append index i to positions list inside the if block

C. Break the loop after first match

D. Use positions = target instead of list

Solution

1. Step 1: Understand requirement to find all matches

   We must collect all indices where target appears, not stop at first.

2. Step 2: Append matching indices to list

   Inside if, add positions.append(i) to store all found positions.

3. Final Answer:

   Append index i to positions list inside the if block -> Option B

4. Quick Check:

   Collect all indices by appending [OK]

Hint: Append all matching indices to list [OK]

Common Mistakes:

• Returning immediately on first match
• Breaking loop early
• Assigning target to positions instead of appending