How to Implement Linear Search in Python

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

tip

Using enumerate() is preferred over range(len(arr)) because it provides both the index and value simultaneously, making the code more readable and less error-prone.

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

info

Both list.index() and the in operator use linear search internally. They are implemented in C (in CPython), making them faster than a Python-level for loop. For production code, prefer these built-in methods over manual implementations.

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

caution

The recursive approach has a recursion depth limit (default ~1000 in Python). For lists longer than about 1000 elements, this will raise a RecursionError. The iterative approach has no such limitation and is preferred for practical use.

# This will fail for large lists:
large_arr = list(range(2000))
linear_search_recursive(large_arr, 1999)  # RecursionError!

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]

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

# Find the first number greater than 10
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

When to Use Linear Search

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

info

For repeated searches on the same data, consider:

• Sorting + Binary Search: O(n log n) setup, then O(log n) per search.
• Hash set/dictionary: O(n) setup, then O(1) per search.
• Linear Search: O(n) per search, no setup needed.

If you search the same list more than log n times, sorting it first and using Binary Search is more efficient.

Linear Search vs. Binary Search

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

Correct: handle with try/except or manual search

arr = [10, 20, 30]

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

# Option 2: Check membership first
index = arr.index(99) if 99 in arr else -1

# Option 3: Custom function (avoids double scan)
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.