Skip to content
Tutorial Reference

How to Implement Linear Search in Python

Learn how to implement linear search in Python with iterative, recursive, and Pythonic approaches, understand its O(n) time complexity, and determine when to use it for unsorted data or custom conditions.

Linear Search is the simplest searching algorithm: it checks each element of a list one by one, from beginning to end, until the target element is found or the list is exhausted. While not the fastest search algorithm, Linear Search is versatile because it works on unsorted data and requires no preprocessing.

In this guide, you will learn how Linear Search works, see multiple Python implementations (iterative, recursive, and Pythonic approaches), understand its time complexity, and know when to use it versus more efficient alternatives.

How Linear Search Works

The algorithm is straightforward:

  1. Start from the first element of the list.
  2. Compare the current element with the target value.
  3. If they match, return the index.
  4. If not, move to the next element.
  5. If the end of the list is reached without finding the target, return -1.

Visual Walkthrough

Array: [10, 50, 30, 70, 80]    Target: 30

Step 1: Compare arr[0]=10 with 30 → No match
Step 2: Compare arr[1]=50 with 30 → No match
Step 3: Compare arr[2]=30 with 30 → Match found! Return index 2

Iterative Implementation

The standard iterative approach loops through each element and returns the index when a match is found:

def linear_search(arr, target):
    """Search for target in arr. Return index if found, -1 otherwise."""
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1


arr = [10, 23, 45, 70, 11, 15]
target = 70

result = linear_search(arr, target)

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

Output:

Element 70 found at index 3

How it works:

  • for i in range(len(arr)) iterates through each index.
  • if arr[i] == target checks if the current element matches.
  • Returns the index immediately on the first match.
  • Returns -1 only after checking every element without finding a match.

Pythonic Implementation Using enumerate()

A more Pythonic version uses enumerate() for cleaner index tracking:

def linear_search(arr, target):
    """Search for target using enumerate for cleaner iteration."""
    for index, value in enumerate(arr):
        if value == target:
            return index
    return -1


arr = [10, 23, 45, 70, 11, 15]
print(linear_search(arr, 70))   # 3
print(linear_search(arr, 99))   # -1

Output:

3
-1

Using Python's Built-in Methods

Python provides built-in ways to perform linear search without writing the loop yourself:

Using list.index()

arr = [10, 23, 45, 70, 11, 15]

try:
    index = arr.index(70)
    print(f"Element found at index {index}")
except ValueError:
    print("Element not found")

Output:

Element found at index 3

Using the in Operator

For a simple existence check (without needing the index):

arr = [10, 23, 45, 70, 11, 15]

if 70 in arr:
    print("Element found")
else:
    print("Element not found")

Output:

Element found

Recursive Implementation

Linear Search can also be implemented recursively, checking one element per call:

def linear_search_recursive(arr, target, index=0):
    """Recursively search for target starting from the given index."""
    if index == len(arr):
        return -1  # Base case: reached end without finding
    if arr[index] == target:
        return index  # Base case: found the target
    return linear_search_recursive(arr, target, index + 1)


arr = [10, 20, 30, 40, 50]
target = 30

result = linear_search_recursive(arr, target)
print(f"Element {target} found at index {result}")

Output:

Element 30 found at index 2

Finding All Occurrences

The basic linear search returns only the first occurrence. To find all indices where the target appears:

def find_all(arr, target):
    """Return a list of all indices where target is found."""
    return [i for i, val in enumerate(arr) if val == target]


arr = [10, 30, 20, 30, 40, 30]
target = 30

indices = find_all(arr, target)

if indices:
    print(f"Element {target} found at indices: {indices}")
else:
    print(f"Element {target} not found")

Output:

Element 30 found at indices: [1, 3, 5]

Searching with a Condition

Linear Search is especially useful when searching by a custom condition rather than exact equality:

def find_first(arr, condition):
    """Return the index of the first element satisfying the condition."""
    for i, val in enumerate(arr):
        if condition(val):
            return i
    return -1


numbers = [3, 7, 12, 5, 18, 9, 24]

index = find_first(numbers, lambda x: x % 2 == 0)
print(f"First even number at index {index}: {numbers[index]}")

index = find_first(numbers, lambda x: x > 10)
print(f"First number > 10 at index {index}: {numbers[index]}")

Output:

First even number at index 2: 12
First number > 10 at index 2: 12

Time and Space Complexity

Case Time Complexity Description
Best case O(1) Target is the first element
Average case O(n) Target is somewhere in the middle
Worst case O(n) Target is the last element or not present
Space complexity O(1) iterative / O(n) recursive Recursive uses stack space

Linear Search is the right choice in specific scenarios:

Scenario Why Linear Search Works
Unsorted data No preprocessing needed; it works on any order
Small lists Overhead of sorting or building a hash table isn't worth it
Single search If you only search once, sorting first (O(n log n)) is slower
Linked lists No random access available; sequential scan is the only option
Custom conditions Searching by a predicate, not just equality
Feature Linear Search Binary Search
Data requirement Works on unsorted data Requires sorted data
Time complexity O(n) O(log n)
Implementation Simple Slightly more complex
Best for Small or unsorted lists Large, sorted lists
Custom conditions ✅ Flexible ❌ Only works with ordering

Common Mistake: Not Handling the "Not Found" Case

A frequent error is forgetting to handle the case where the element doesn't exist:

Wrong: crashes when element is missing

arr = [10, 20, 30]
index = arr.index(99)  # ValueError: 99 is not in list
arr = [10, 20, 30]

try:
    index = arr.index(99)
except ValueError:
    index = -1

index = arr.index(99) if 99 in arr else -1

def safe_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

Summary

Linear Search is the most fundamental searching algorithm in computer science. Key takeaways:

  • How it works: Check each element sequentially until the target is found or the list ends.
  • Time complexity: O(n), which is proportional to the list size.
  • Use built-in methods (in, list.index()) for production Python code; they are faster than manual loops.
  • Best suited for unsorted data, small lists, single searches, and custom search conditions.
  • Consider alternatives like Binary Search (sorted data) or hash-based lookups (repeated searches) for better performance on large datasets.
  • The iterative approach is preferred over recursion to avoid stack overflow on large lists.
Navigation