Linear Search in Python Program: All You Need to Know

A linear search in Python program is a simple yet powerful algorithm used to find an element in a list by checking each item sequentially. The linear search algorithm is crucial for beginners learning Python and data structures.

In this blog, you will dive into the concept of linear search, how to implement it in Python, and explore different variations of the program to enhance your understanding.

What is Linear Search in Python?

Linear search is a straightforward algorithm used to find an element in a list by checking each item one by one, starting from the beginning. It moves through the list sequentially until it finds the target element or reaches the end of the list.

This method works well for unsorted data because it doesn't require any order in the list. It’s especially useful when you are dealing with small datasets or when a simple solution is needed for finding elements.

For example, if you need to find a missing student ID in an unsorted database, linear search is ideal as it allows you to quickly iterate through the entries without needing sorting or complex algorithms.

In Python, implementing the linear search algorithm is easy and practical, especially when efficiency is not the top priority. You can use this technique to search for specific values in a variety of real-world applications, like finding a name in an unsorted list of contacts.

Comparing Linear Search with Other Search Algorithms

Different search algorithms offer varying advantages based on the dataset's size and structure; understanding these differences will help you in choosing the most efficient approach.

Here’s a comparison of Linear Search with other popular search algorithms:

In this comparison, Linear Search is simple but not the most efficient for larger datasets, especially when compared to Binary Search or more advanced algorithms like Jump Search and Interpolation Search.

Also Read: Linear Search vs Binary Search: Key Differences Explained Simply

Now that you understand how linear search works, let’s dive into the practical steps to implement the linear search algorithm in Python. 

How Do You perform linear search in Python?

To perform a linear search in Python, you need to check each element of the list one by one until you find the target. The process is simple:

1. Start from the first element of the list.
2. Compare the current element with the target.
3. If they match, return the index where the target is found.
4. If not, move to the next element and repeat the comparison.
5. If you reach the end of the list without finding the target, return -1 to indicate that the target is not in the list.

Here’s an example to help you understand how it works: 

def linear_search(arr, target):
    for index in range(len(arr)):
        if arr[index] == target:
            return index  # Return the index if found
    return -1  # Return -1 if the element is not found

# Example usage:
numbers = [10, 20, 30, 40, 50]
target = 30
result = linear_search(numbers, target)
print(f"Element {target} found at index: {result}")

Output: 

Element 30 found at index: 2

Explanation:

• Function Parameters:
  • arr: The list of elements you want to search through.
  • target: The element you're looking for in the list.
• How the List and Target Work Together:
  • The function iterates over each element in the list using the for loop and compares it with the target.
  • If a match is found, the function returns the index of the target.
  • If no match is found after checking all elements, the function returns -1.

This simple linear search technique works well for small or unsorted lists. 

Next, let's explore Python programs for linear search, covering various methods to implement and enhance your understanding of the algorithm.

Python Programs for Linear Search

In this section, you'll explore various Python implementations of linear search, each tailored to different use cases and methods for better understanding and optimization.

Python Program for Linear Search - Basic

In this example, we will implement a simple linear search in a Python program using an iterative approach. This approach is easy to understand and is ideal for beginners. The program will search for an element in a list by checking each item one by one. 

def linear_search(arr, target):
    # Iterate through the list
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Element found, return index
    return -1  # Element not found

# Example usage
arr = [5, 2, 9, 1, 5, 6]
target = 9
result = linear_search(arr, target)

# Output result
if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found.")

Output: 

Element 9 found at index 2

Explanation:

• The function linear_search accepts two parameters: arr (the list of elements) and target (the value you are searching for).
• It iterates through the list, checking each element at index i.
• If a match is found, it returns the index of the element. If no match is found by the end of the loop, it returns -1, indicating the element is not present in the list.
• In the example, the target value 9 is found at index 2, so it prints that index.

Edge Cases

While Linear Search is straightforward and effective for many cases, there are several edge cases that may arise during its implementation. 

Let’s explore some common edge cases for the given Python program:

1. Empty List: If the list is empty, the search should immediately return -1, indicating that the element is not found.
   • Edge Case: arr = [], target = 5
   • Expected Result: Element 5 not found.
2. Element Not in the List: If the target element is not present in the list, the program should correctly return -1 after checking all elements.
   • Edge Case: arr = [1, 2, 3], target = 5
   • Expected Result: Element 5 not found.
3. Element at the Beginning: If the target element is the first item in the list, the program should return 0 without needing to iterate further.
   • Edge Case: arr = [9, 2, 3], target = 9
   • Expected Result: Element 9 found at index 0
4. Multiple Occurrences of Target: If the target element appears multiple times in the list, the program will return the index of the first occurrence.
   • Edge Case: arr = [4, 5, 2, 5, 6], target = 5
   • Expected Result: Element 5 found at index 1
5. Large List: For large datasets, Linear Search will take time proportional to the size of the list, potentially causing performance issues. This is more of a limitation than an edge case, but it’s important to note when working with large datasets.
   • Edge Case: arr = [i for i in range(1000000)], target = 999999
   • Expected Result: Element 999999 found at index 999999

Also Read: Selection Sort Algorithm in Data Structure: Code, Function & Example

This approach is straightforward and well-suited for small datasets or when data is unsorted.

Python Program for Linear Search - Iterative Approach

This method involves looping through the array one element at a time, comparing each element to the target, and returning the index when the element is found. 

def linear_search_iterative(arr, target):
    for i in range(len(arr)):  # Iterate through the array
        if arr[i] == target:  # If the element matches
            return i  # Return the index of the element
    return -1  # Return -1 if the element is not found

# Example usage
arr = [12, 34, 54, 2, 3]
target = 54
result = linear_search_iterative(arr, target)

if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found.")

Output: 

Element 54 found at index 2

Explanation:

• The linear_search_iterative function checks each element in the list, starting from the first item.
• If it finds the target, it returns the index of that element.
• If no match is found after iterating through the entire list, it returns -1.

Edge Cases

The Iterative Linear Search method is useful for searching through an array element by element, and it handles various edge cases well. However, it's important to consider some specific scenarios that may affect its behavior. 

Let’s explore the common edge cases for this implementation:

1. Empty Array: If the array is empty, the program should immediately return -1 as there are no elements to search through.
   • Edge Case: arr = [], target = 5
   • Expected Result: Element 5 not found.
2. Element Not Present in the Array: When the target element is not present in the array, the function should check all elements and return -1 at the end.
   • Edge Case: arr = [10, 20, 30], target = 40
   • Expected Result: Element 40 not found.
3. Element at the Start: If the target element is the first element in the array, the program should return the index 0 without needing to iterate through the rest of the array.
   • Edge Case: arr = [5, 12, 15], target = 5
   • Expected Result: Element 5 found at index 0
4. Element at the End: If the target element is the last element in the array, the program should successfully return its index after iterating through all other elements.
   • Edge Case: arr = [1, 2, 3, 4], target = 4
   • Expected Result: Element 4 found at index 3
5. Multiple Occurrences: If the target element appears multiple times in the array, the program will return the index of the first occurrence.
   • Edge Case: arr = [1, 2, 3, 2, 4], target = 2
   • Expected Result: Element 2 found at index 1
6. Large Arrays: For large datasets, this iterative approach could result in longer execution times, especially when the element is near the end of the list. This isn’t an edge case in functionality, but it’s important to consider for performance in large-scale applications.
   • Edge Case: arr = [i for i in range(1000000)], target = 999999
   • Expected Result: Element 999999 found at index 999999

This approach is useful for its simplicity and effectiveness, especially when dealing with small or unsorted datasets. 

Python Program for Linear Search - Recursive Approach

The linear search using a recursive approach will repeatedly call itself until the element is found or the end of the list is reached. 

def linear_search_recursive(arr, target, index=0):
    # Base case: if we've checked all elements
    if index == len(arr):
        return -1
    if arr[index] == target:  # If the element matches
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive call

# Example usage
arr = [5, 3, 7, 2, 9]
target = 7
result = linear_search_recursive(arr, target)

if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found.")

Output: 

Element 7 found at index 2

Explanation:

• The linear_search_recursive function calls itself with an incremented index until it finds the target or reaches the end of the list.
• If the element is found, it returns the index; otherwise, it keeps calling itself.
• When the end of the list is reached, it returns -1.

This approach provides a more elegant, recursive solution but may not be as efficient as the iterative approach for large datasets due to stack depth. 

Edge Cases

The recursive approach to linear search can handle several edge cases effectively. However, there are some situations where special attention is needed:

1. Empty Array: If the array is empty, the function should immediately return -1 since there are no elements to search.
   • Edge Case: arr = [], target = 5
   • Expected Result: Element 5 not found.
2. Element Not in the Array: If the target element isn’t in the array, the recursion should reach the end and return -1.
   • Edge Case: arr = [1, 2, 3], target = 4
   • Expected Result: Element 4 not found.
3. Element at the First Index: If the target element is the first element in the array, the recursion should return 0 immediately.
   • Edge Case: arr = [5, 3, 7], target = 5
   • Expected Result: Element 5 found at index 0
4. Element at the Last Index: If the target element is the last element, the recursion should go through the entire array and return the correct index.
   • Edge Case: arr = [1, 2, 3], target = 3
   • Expected Result: Element 3 found at index 2
5. Multiple Occurrences: Like the iterative approach, if the target appears multiple times, the function will return the index of the first occurrence.
   • Edge Case: arr = [2, 3, 5, 3], target = 3
   • Expected Result: Element 3 found at index 1
6. Deep Recursion: For very large arrays, this recursive approach might hit the recursion limit (default is 1000), leading to a RecursionError. This should be handled if working with large datasets.
   • Edge Case: arr = [i for i in range(1000000)], target = 999999
   • Expected Result: RecursionError if recursion depth exceeds limit.

Also Read: Tower of Hanoi Algorithm Using Recursion: Definition, Use-cases, Advantages

Python Program for Linear Search - RegEx Method

This method is particularly helpful when searching for string patterns or substrings, making it an interesting variation of the traditional linear search.

import re

def linear_search_regex(arr, target):
    pattern = re.compile(re.escape(str(target)))  # Create a RegEx pattern
    for i, item in enumerate(arr):
        if pattern.search(str(item)):  # Search for the pattern in the item
            return i  # Return index if match is found
    return -1  # Return -1 if not found

# Example usage
arr = ['apple', 'banana', 'cherry', 'date']
target = 'cherry'
result = linear_search_regex(arr, target)

if result != -1:
    print(f"Element {target} found at index {result}")
else:
    print(f"Element {target} not found.")

Output: 

Element cherry found at index 2

Explanation:

• The linear_search_regex function uses Python’s re library to compile a RegEx pattern for the target element.
• It then iterates through the list, searching each item for a match using pattern.search.
• If a match is found, it returns the index of the element; otherwise, it returns -1.

Edge Cases

The RegEx method of linear search is useful for searching string patterns and substrings, but there are several edge cases to consider:

1. Empty Array: If the array is empty, the function should immediately return -1, as there are no elements to search.
   • Edge Case: arr = [], target = 'apple'
   • Expected Result: Element apple not found.
2. Element Not in the Array: If the target string is not present, the RegEx search should return -1 after checking all items.
   • Edge Case: arr = ['cat', 'dog', 'mouse'], target = 'elephant'
   • Expected Result: Element elephant not found.
3. Case Sensitivity: RegEx searches are case-sensitive by default, so searching for 'apple' won't match 'Apple'.
   • Edge Case: arr = ['Apple', 'banana', 'cherry'], target = 'apple'
   • Expected Result: Element apple not found.
4. Substring Matches: If the target is a substring of an element, the program will still return the index of the match. This may or may not be the desired behavior.
   • Edge Case: arr = ['applepie', 'banana', 'cherry'], target = 'apple'
   • Expected Result: Element apple found at index 0
5. Searching for Non-String Elements: When searching for non-string elements, the function converts each item in the array to a string. This could lead to unexpected results if the items in the list are not naturally string-like.
   • Edge Case: arr = [123, 456, 789], target = 123
   • Expected Result: Element 123 found at index 0
6. Special Characters in Target: If the target contains special characters (e.g., *, +, ?), they need to be escaped to avoid unintended behavior in RegEx. The program handles this via re.escape(), but it’s something to consider when dealing with complex patterns.
   • Edge Case: arr = ['*apple', 'banana', 'cherry'], target = '*apple'
   • Expected Result: Element *apple found at index 0

To further enhance your Python skills, upGrad offers tailored programs designed to take your expertise to the next level.

How upGrad Advances Your Expertise in Python Programming?

upGrad’s Python and programming-related courses offer a hands-on approach to mastering key algorithms like linear search. These programs deepen your understanding of data manipulation and algorithmic thinking, providing you with real-world applications.

Here are some of the top courses you can check out: 

• Learn Python Libraries: NumPy, Matplotlib & Pandas
• Executive PG Diploma in Data Science & AI
• Post Graduate Certificate in Data Science & AI (Executive)
• Executive Diploma in Machine Learning and AI by IIIT Bangalore

Start with upGrad's free courses to build a solid Python foundation, and unlock advanced opportunities in data science and AI.

For personalized career guidance, consult upGrad’s expert counselors or visit our offline centers to find the best course tailored to your goals.

Unlock the power of data with our popular Data Science courses, designed to make you proficient in analytics, machine learning, and big data!

Explore our Popular Data Science Courses

Elevate your career by learning essential Data Science skills such as statistical modeling, big data processing, predictive analytics, and SQL!

Top Data Science Skills to Learn

Stay informed and inspired  with our popular Data Science articles, offering expert insights, trends, and practical tips for aspiring data professionals!

Read our popular Data Science Articles