Start learning free

LESSON 148 OF 410 · LOOPING OVER LIST INDICES

Linear Searching in Python (O(n) Time Complexity)

Practice Read the full explanation

Given an array of integers nums, return the index of a given value.

If the value doesn't exist, return -1.

Example 1:

Input: nums = [1, 2, 4, 5], value = 4
Output: 2
Explanation: nums[2] is 4

Note:

Your algorithm should run in O(n) time and use O(1) space.


Hints:

We should try out each element in nums until we find one equal to value and return its index. How can we achieve this?

With a for loop, of course! We can use a variable num to iterate through the elements and an if statement to check if num is equal to value. If it is, we have found the solution! But...
This is how we look for value in nums, but there's a problem. The problem asks us to return the index of that element, and by iterating like this we only know the value of the current element, not its index. How can we fix this?

We should use another method of iterating through an array: by indices! Let's use an index variable i to go through every index between 0 and len(nums) - 1.
For each index i, the index is i and the value is the element of nums at that index. If that element is equal to value, we return i.
What if we don't have any element equal to value? Where should we return -1?

After the loop, outside of it, we return -1.
If we reach that line, this means the for loop terminated naturally without returning any index. If we had returned an index, we wouldn't even be executing this line of code as the program would have finished.

We have a for loop that performs exactly n iterations (where n is the length of nums), thus the Time Complexity is O(n).
The only extra space we use is the iterator variable i inside the loop, thus the Extra Space used is O(1).

Video Solution:

STEP 1 OF 3
    Ctrl + Enter to check

    PYTHON · LOOPING OVER LIST INDICES

    Linear Search in Python, explained

    Understanding the Problem

    The core challenge of this problem is to find the index of a given value in an array of integers. This is a fundamental problem in computer science known as linear search. Linear search is significant because it is the simplest search algorithm and is used in various applications where the dataset is small or unsorted.

    Potential pitfalls include not handling the case where the value is not present in the array, which should return -1.

    Approach

    To solve this problem, we can use a simple linear search algorithm. The idea is to iterate through each element in the array and check if it matches the given value. If a match is found, we return the index. If no match is found after checking all elements, we return -1.

    Let's break down the approach:

    1. Initialize a loop to iterate through each element in the array.
    2. For each element, check if it matches the given value.
    3. If a match is found, return the current index.
    4. If the loop completes without finding a match, return -1.

    Algorithm

    Here is a step-by-step breakdown of the algorithm:

    1. Start a loop from index 0 to the length of the array minus one.
    2. In each iteration, compare the current element with the given value.
    3. If they are equal, return the current index.
    4. If the loop completes without finding a match, return -1.

    Code Implementation

    def linear_search(nums, value):
    # Iterate through each index in the array
    for i in range(len(nums)):
        # Check if the current element is equal to the given value
        if nums[i] == value:
            return i  # Return the index if a match is found
    return -1  # Return -1 if no match is found

# Example usage
nums = [1, 2, 4, 5]
value = 4
print(linear_search(nums, value))  # Output: 2

    Complexity Analysis

    The time complexity of this algorithm is O(n) because in the worst case, we may need to check all elements in the array. The space complexity is O(1) because we are not using any extra space that scales with the input size.

    Edge Cases

    Consider the following edge cases:

    • The array is empty. The function should return -1.
    • The value is not present in the array. The function should return -1.
    • The value is present multiple times. The function should return the index of the first occurrence.

    Examples:

    print(linear_search([], 4))  # Output: -1
print(linear_search([1, 2, 3], 4))  # Output: -1
print(linear_search([1, 2, 4, 4], 4))  # Output: 2

    Testing

    To test the solution comprehensively, consider the following test cases:

    • Simple cases with small arrays.
    • Edge cases with empty arrays and values not present.
    • Cases with multiple occurrences of the value.

    Example test cases:

    assert linear_search([1, 2, 4, 5], 4) == 2
assert linear_search([1, 2, 3], 4) == -1
assert linear_search([], 4) == -1
assert linear_search([1, 2, 4, 4], 4) == 2

    Thinking and Problem-Solving Tips

    When approaching such problems, consider the following tips:

    • Understand the problem requirements and constraints.
    • Start with a simple, brute-force solution to understand the problem better.
    • Optimize the solution by considering time and space complexity.
    • Test the solution with various test cases, including edge cases.

    To improve problem-solving skills, practice solving similar problems and study different algorithms and their applications.

    Conclusion

    In this blog post, we discussed the linear search algorithm, its implementation in Python, and its complexity analysis. Linear search is a fundamental algorithm that is easy to understand and implement. By practicing such problems, you can improve your problem-solving skills and understanding of basic algorithms.

    Additional Resources

    For further reading and practice, consider the following resources:

    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free