Linear Search in Python

Examples

To learn how linear search works, let’s consider a few examples:

• Finding a number in a list:
   
• Suppose you have a list: [4, 2, 8, 6, 7]
   
• You want to check if the number 6 is in the list.
   
• A linear search would check each element from left to right: first 4, then 2, then 8, and when it reaches 6, it confirms that the number is present.
   
• Searching for a character in a string:
   
• Imagine you have the string "hello" and you need to find if the letter 'e' is part of it.
   
• Starting at 'h', the search moves to 'e' and finds the character on the second position.

Python Program for Linear Search: Iterative Approach

To implement a linear search using Python in an iterative way, we write a function that loops through all elements in the list and checks if each element matches the target value. Here’s how you can do it step by step:

• Python

Python

def linear_search(arr, x):
    """
    This function returns the index of x in arr if present, else returns -1.
    """
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

# Example usage:
arr = [5, 3, 8, 6, 7]
x = 6
result = linear_search(arr, x)
if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found")

You can also try this code with Online Python Compiler

Run Code

Output

Element found at index 3

This code snippet defines a function linear_search that takes two parameters: arr (the list to search in) and x (the element to find). It iterates over each element in the list, compares it with x, and if it finds a match, it returns the index of the element. If the loop completes without finding the element, it returns -1 indicating that the element is not in the list.

Python Program for Linear Search: Recursive Approach

Implementing linear search using recursion involves a function calling itself with updated parameters until a condition is met. Here's how you can perform a linear search in Python using a recursive method:

• Python

Python

def recursive_linear_search(arr, index, x):
    """
    A recursive function to search x in arr[] starting from index.
    Returns index of x if it is present, else returns -1.
    """
    if index >= len(arr):
        return -1  # If index is greater than or equal to the length of the array, return -1.
    elif arr[index] == x:
        return index  # If the element at the current index matches x, return the index.
    return recursive_linear_search(arr, index + 1, x)  # Recur for the rest of the array.

# Example usage:
arr = [10, 20, 30, 40, 50]
x = 30
result = recursive_linear_search(arr, 0, x)  # Start searching from index 0
if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found")

You can also try this code with Online Python Compiler

Run Code

Output

Element found at index 2

Explanation:

• Function Definition:
   
• def recursive_linear_search(arr, index, x):
   
• This defines a recursive function named recursive_linear_search with three parameters: arr (the array), index (the starting index for the search), and x (the element to find).
   

Base Cases:

• Check if the index has reached the end of the array without finding the element (index >= len(arr)), in which case return -1.
   
• Check if the element at the current index is the one we're looking for (arr[index] == x). If so, return that index.
   

Recursive Call:

• If neither base case is true, the function calls itself with the next index (index + 1).
   

Using the Function:

• Initialize the array and the element to be searched.
   
• Call the function starting from the first index (0).
   
• Print the result based on whether the element was found or not.

Python Program for Linear Search Using re Method

Another creative way to implement linear search in Python is by using the re (regular expression) module. This method is particularly useful when searching for patterns or specific strings within text data. Here’s how to perform a linear search to find a substring in a string using the re module:

• Python

Python

import re

def re_linear_search(text, pattern):
    """
    This function uses regular expressions to find a pattern in a given text.
    Returns the starting index of the pattern if found, else returns -1.
    """
    match = re.search(pattern, text)
    if match:
        return match.start()  # Return the starting index of the first match.
    return -1  # If no match is found, return -1.

# Example usage:
text = "Hello, welcome to the world of Python programming."
pattern = "Python"
result = re_linear_search(text, pattern)
if result != -1:
    print(f"Pattern found at index {result}")
else:
    print("Pattern not found")

You can also try this code with Online Python Compiler

Run Code

Output

Pattern found at index 31

Explanation:

• Importing Module:
   
• import re imports the Python module for regular expressions, which provides regex matching operations similar to those found in Perl.
   

Function Definition:

• def re_linear_search(text, pattern):
   
• This function is designed to search for a pattern within a text string using regular expressions.
   

Searching for the Pattern:

• match = re.search(pattern, text)
   
• The re.search() function searches the text for the first location where the regular expression pattern produces a match. It returns a match object if the search is successful.
   

Check and Return the Result:

• If a match is found (if match:), the function returns the starting index of the match (match.start()).
   
• If no match is found, the function returns -1.
   

Example Usage:

• The function is tested with a sample text and a pattern to search for. The result is printed based on whether the pattern is found.

Algorithm of Linear Search

The algorithm for linear search is straightforward. It sequentially checks each element of the list until a match is found or the list is exhausted. Here’s the step-by-step breakdown:

• Start from the first element: Begin at the first index of the list.
   
• Compare the target element with the current element in the list: If they match, you have found the element, and the search can terminate successfully.
   
• Move to the next element: If the current element is not the target, move to the next element in the list.
   
• Repeat the process: Continue steps 2 and 3 until the element is found or the end of the list is reached.
   
• Return the result: If the target element is found, return the index at which it was found. If the end of the list is reached without finding the target, return -1, indicating that the element is not in the list.
   

This algorithm is simple and does not require any advanced setup or preconditions, making it ideal for cases where the list is not sorted and little is known about the data. Its simplicity also makes it very easy to explain to beginners who are just learning about searching techniques in computer science.

Time and Space Complexity of Linear Search

Understanding the time and space complexity of linear search is crucial for assessing its efficiency. 

Time Complexity

• Best-case scenario: O(1). This happens when the target element is the first element of the list.
   
• Worst-case scenario: O(n). This occurs when the target element is at the last position of the list or not present at all. In these cases, the algorithm checks every element in the list.
   
• Average-case scenario: O(n). On average, the search might go through half the list, but since we consider big O notation for approximations, it simplifies to O(n).

Space Complexity

Space Complexity: O(1). Linear search is an in-place algorithm, which means it does not require any additional storage that grows with the input size. The space used is constant and does not depend on the size of the list being searched.

These complexities make linear search a simple but potentially inefficient choice for large datasets, especially when frequent searches are expected. It is most suitable for small to medium-sized lists or when the list elements are not sorted and other faster search methods (like binary search) cannot be applied.

Frequently Asked Questions

What happens if there are multiple occurrences of the target in the list?

Linear search returns the index of the first occurrence of the target element in the list. To find all occurrences, the algorithm would need to continue searching through the list even after the first match is found.

Is linear search suitable for searching in sorted lists?

While linear search can be used on sorted lists, it is not the most efficient method. For sorted lists, algorithms like binary search are more appropriate because they use the list's order to significantly reduce the search time.

Can linear search be used with data structures other than lists?

Yes, linear search is a versatile algorithm that can be applied to any data structure that allows sequential access to its elements, such as arrays, linked lists, and even strings for character or substring searches.

Conclusion

In this article, we have learned about the implementation of  linear search in Python. We explored its basic concept, iterative and recursive implementations, and a unique method using regular expressions. We also discussed the algorithm's time and space complexities and addressed common questions related to its use. Linear search is a straightforward algorithm that, despite its simplicity, plays a critical role in solving real-world searching problems, especially when dealing with unsorted data or data structures that support only sequential access.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.