Linear Search | Explained in Python

Given an array, arr of n integers, and an integer element x, find whether element x is present in the array. Return the index of the first occurrence of x in the array, or -1 if it doesn’t exist.

Here’s the [Problem Link] to begin with.

1. What does the question says?

This question is asking us to find the position (0-based index) of a specified value in an array. Specifically:

1. We are provided:
   • An integer n denoting the size of the array.
   • An integer num which is the target element to be searched.
   • An array arr of length n.
2. Our task is to determine whether num is present in the array arr.
   • If it is present, return the index (0-based) of its first occurrence.
   • If it is not found in the array, return −1.

Essentially, the question is about scanning the array and identifying if the target value num appears. If so, we should report the position where it appears for the first time. If it never appears, we return −1.

2. How do we approach the problem?

To solve this, we typically employ 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.

3. 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

4. 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.

5. Dry Run

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

6. Potential Edge Cases

1. Array of Size 1:
   • If arr = [7] and num = 7, returns 0. Otherwise, -1.
2. Value Not Present:
   • If arr = [1, 2, 3] and num = 4, returns -1.
3. Multiple Occurrences:
   • If arr = [2, 7, 7, 9] and num = 7, returns the first index (1).
4. Value at the Last Position:
   • If arr = [2, 3, 4, 5, 7] and num = 7, returns 4.
5. Empty Array (if allowed):
   • If n = 0, returns -1 immediately (though constraints may not allow this case).

7. Time and Space Complexity

• Time Complexity: O(n) in the worst case, because we may scan 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.