Linear Search in Python | Explained with Images and Examples

In this article we’ll guide you through on how to implement Linear Search in Python [Problem Link]. We will see the only way to solve this and also the dry run with images to understand the solution properly. So let’s begin.

Understand the problem

You are given an array (or list) of integers and a target value. The goal is to find whether the target exists in the array and, if so, at which index it appears. In a linear search, you start from the beginning of the array and check each element one by one until you find the target or reach the end of the array.

Example 1

• Array: [3, 1, 4, 7, 9]
• Target: 4

In a linear search, you would check elements in this order:

1. Is 3 equal to 4? No.
2. Is 1 equal to 4? No.
3. Is 4 equal to 4? Yes.

Here, you’d find the target at index 2 (0-based indexing).

Example 2

• Array: [10, 20, 30, 40]
• Target: 50

You would scan through each element:

1. 10? Not a match.
2. 20? Not a match.
3. 30? Not a match.
4. 40? Not a match.

You reach the end without finding 50, so the target does not exist in the array.

Example 3

• Array: [5, 5, 5, 5]
• Target: 5

In this scenario, every element is the same as the target. If you’re just checking for existence, you’ll find the target right at index 0. If you were looking for all occurrences, you’d note that it appears at every index (0, 1, 2, and 3).

Also read about a DSA Problem on how to Find the Union of 2 Sorted Arrays with Duplicates.

Implementing and Understanding Linear Search

How do we approach the problem?

To solve this, we typically use a method known as linear search:

1. Definition of Linear Search
   • Linear search involves traversing the array from the start to the end and comparing each element to the target, num.
2. Why Linear Search Works Here
   • We do not have any conditions like a sorted array that might allow more specialized techniques (e.g., binary search).
   • Linear search is simple and ensures that every element is checked, so we cannot miss the target if it is indeed present.
3. Core Idea
   • Start at index 0.
   • Compare arr[i] with num.
   • If they match, return i immediately.
   • If not, move to the next index and repeat.
   • If we reach the end of the array without a match, return −1.

Thus, by carefully checking each element in order, we can reliably determine if num exists in arr, and if so, at which index we first encounter it.

Code Implementation

def linearSearch(n: int, num: int, arr: [int]) -> int:
    for i in range(0, len(arr)):
        if arr[i] == num:
            return i
    return -1

Step-by-Step Explanation

1. Loop Initialization: Start from index 0 and go up to len(arr) – 1.
2. Comparison: At each index i, check if arr[i] equals num.
3. Early Return: If they match, return i.
4. Conclusion: If no match is found by the end, return -1.

Dry Run (with images)

Let’s go through the code step by step, using images to see the detailed dry run process.

Time and Space Complexity Analysis

• Time Complexity: O(n) in the worst case, because we may iterate each element once.
• Space Complexity: O(1), as we only use a few auxiliary variables.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.