Linear Search — Implement linear search over a list - Python

SECTION 1

Historical Context & Motivation

Searching for information is one of the most fundamental tasks in computing. Long before computers existed, people needed to find specific items in collections — a name in a phone book, a word in a dictionary, or a record in a filing cabinet. The most intuitive way to search is simply to start at the beginning and check each item one at a time. This approach, known as linear search (also called sequential search), has been a cornerstone of algorithm design since the earliest days of computer science.

1940s • Early Stored-Program Computers

The first electronic computers, such as ENIAC and EDVAC, stored data in sequential memory. Searching through data meant reading one memory location at a time — essentially performing linear search by hardware necessity.

1946 • John von Neumann's Merge Sort Paper

Von Neumann described sorting and searching algorithms for stored-program computers. Linear search was recognized as the baseline method against which more efficient algorithms would be measured.

1962 • Knuth Begins 'The Art of Computer Programming'

Donald Knuth's monumental textbook series formally analyzed sequential searching, establishing its time complexity and comparing it to binary search and hashing techniques.

1991 • Python Is Created

Guido van Rossum released Python, a language designed for readability. Python's built-in in operator uses linear search on lists, making the algorithm accessible to beginners.

Even today, linear search remains relevant. When data is unsorted, when the collection is small, or when you only need to search once, linear search is often the most practical choice. Understanding this algorithm is the first step toward appreciating why faster search methods like binary search and hash tables were developed — and when they are actually needed.

SECTION 2

Core Principles & Definitions

Linear search is built on a few straightforward ideas. Before diving into code, let's establish the key concepts that define how the algorithm works and why it behaves the way it does.

Sequential Traversal

The algorithm visits each element in the list in order, starting from index 0 and moving forward. It does not skip elements or jump around.

Target Comparison

At each position, the current element is compared to the target value — the item you're searching for. If they match, the search succeeds.

Return the Index

When a match is found, the algorithm returns the index (position) of the matching element. This tells the caller exactly where the target lives in the list.

Handling 'Not Found'

If the algorithm reaches the end of the list without finding a match, it returns a sentinel value (commonly -1 or None) to signal that the target is absent.

No Sorting Required

Unlike binary search, linear search works on any list — sorted or unsorted. This flexibility is one of its greatest strengths.

✦

KEY TAKEAWAY

Think of linear search like looking for a specific book on a shelf that isn't organized in any particular order. You start at the left end and check each book's title one by one until you find the one you want — or you reach the end of the shelf and know it's not there. There's no shortcut when the shelf isn't sorted.

SECTION 3

Visual Explanation

The following diagram illustrates a linear search scanning through a list of six elements to find the target value 42. Each step shows the pointer moving from left to right, comparing the current element against the target.

The search moves left to right through the list. Red-highlighted cells are mismatches. At Step 4, the algorithm finds 42 at index 3 and returns immediately — the remaining elements are never examined.

Notice that the algorithm stops as soon as it finds a match. This is called early termination — there's no reason to keep checking elements after you've already found what you're looking for. In the best case, the target is the very first element and only one comparison is needed. In the worst case, the target is the last element (or not present at all), and every element must be checked.

SECTION 4

Time Complexity & Mathematical Framework

To analyze how efficient an algorithm is, computer scientists use Big-O notation, which describes how the running time grows as the input size increases. For linear search, we measure efficiency by counting the number of comparisons the algorithm makes.

BEST CASE

T(n) = O(1)

The target is the first element. Only 1 comparison is needed, regardless of the list size n. This is called constant time.

WORST CASE

T(n) = O(n)

The target is the last element or is absent. The algorithm checks all n elements. This is called linear time — double the list size, and the work roughly doubles.

AVERAGE CASE

T(n) = O(n/2) = O(n)

On average, if the target is equally likely to be at any position, the algorithm checks about n/2 elements. In Big-O notation, constant factors are dropped, so this simplifies to O(n).

SPACE COMPLEXITY

S(n) = O(1)

Linear search uses only a fixed amount of extra memory — a loop variable and the target value — regardless of how large the list is. This makes it very memory-efficient.

To put this in practical terms: if you have a list of 1,000 elements, linear search might check up to 1,000 elements. If the list grows to 1,000,000 elements, the worst case becomes 1,000,000 comparisons. The relationship between input size and work is a straight line — hence the name linear search.

SECTION 5

Implementation in Python

Now let's translate the algorithm into Python code. There are several ways to implement linear search, and understanding the variations helps you choose the right approach for different situations.

Version 1: Using a for Loop with range()

The most explicit implementation uses range(len(lst)) to iterate through indices. The function linear_search(lst, target) takes two parameters: the list to search and the value to find. It returns the index of the target if found, or -1 if the target is not in the list.

Two implementations of linear search in Python. Version 1 uses range(len(lst)) for explicit index tracking. Version 2 uses enumerate() for a cleaner, more Pythonic style. Both produce identical results.

How the Code Works Step by Step

Line 1: The function accepts lst (the list to search) and target (the value you're looking for).
Line 2: The for loop iterates through every valid index from 0 to len(lst) - 1.
Line 3: The if statement checks whether the element at position i matches the target.
Line 4: If there's a match, the function immediately returns the index i — this is the early termination.
Line 5: If the loop finishes without finding the target, return -1 signals that the target is absent.

💡

Python's Built-in Alternative

Python provides the in operator (e.g., 42 in my_list) and the .index() method, both of which internally perform a linear search. Writing your own implementation helps you understand what's happening under the hood and prepares you for situations where you need to customize the search behavior.

SECTION 6

Worked Example

Let's trace through a complete example where the target is not found in the list, so we can see the algorithm check every element.

Searching for 50 in [15, 8, 23, 42, 16]

1
Step 1 — Set Up the Search

We call linear_search([15, 8, 23, 42, 16], 50). The list has n = 5 elements, so the loop will iterate with i taking values 0, 1, 2, 3, and 4.
2
Step 2 — Check Index 0

lst[0] = 15. Is 15 == 50? No. The loop continues to the next index.

15 ≠ 50 → continue
3
Step 3 — Check Index 1

lst[1] = 8. Is 8 == 50? No.

8 ≠ 50 → continue
4
Step 4 — Check Index 2

lst[2] = 23. Is 23 == 50? No.

23 ≠ 50 → continue
5
Step 5 — Check Index 3

lst[3] = 42. Is 42 == 50? No.

42 ≠ 50 → continue
6
Step 6 — Check Index 4

lst[4] = 16. Is 16 == 50? No. This is the last index, so the loop ends.

16 ≠ 50 → loop ends
7
Step 7 — Return 'Not Found'

The loop has completed without finding a match. The function reaches return -1, indicating that 50 is not in the list. A total of 5 comparisons were made — one for each element.

Return −1 (not found)

SECTION 7

Strengths & Limitations

Linear search has clear advantages and disadvantages. Understanding both helps you decide when it's the right tool and when you should consider alternatives.

Aspect	Strengths ✓	Limitations ✗
Simplicity	Extremely easy to understand, write, and debug — just a few lines of code	Too simple for performance-critical applications with large datasets
Data Requirements	Works on unsorted data — no preprocessing needed	Cannot exploit sorted order to speed up the search
Speed	Fast for small lists (under ~100 elements), where overhead of fancier algorithms outweighs the benefit	O(n) worst case — becomes impractical for very large lists (millions of elements)
Memory	O(1) space — uses almost no extra memory	No limitation in this category
Flexibility	Works on any data type that supports equality comparison (==)	Returns only the first occurrence by default — finding all occurrences requires modification

Linear Search: Strengths vs. Limitations

🎯

WHEN TO USE LINEAR SEARCH

Think of linear search like using your eyes to scan a parking lot for your car. If the lot has 10 spaces, scanning every spot is no big deal. But if you're in a lot with 10,000 spaces, you'd much rather have a system — like remembering which section you parked in. That's the idea behind more advanced search algorithms. Use linear search when the 'parking lot' is small or when there's no organizational system to take advantage of.

SECTION 8

Connection to Binary Search & Advanced Algorithms

Linear search is the foundation upon which other search algorithms are understood. The most important comparison is with binary search, which is dramatically faster — but requires the list to be sorted first.

Feature	Linear Search	Binary Search
Time Complexity (Worst)	O(n)	O(log n)
Requires Sorted Data?	No	Yes
Comparisons for 1,000 items	Up to 1,000	Up to 10
Comparisons for 1,000,000 items	Up to 1,000,000	Up to 20
Implementation Difficulty	Very easy	Moderate (off-by-one errors are common)
Best Use Case	Small or unsorted lists	Large, sorted lists searched repeatedly

Linear Search vs. Binary Search

The difference in scale is astonishing. For a list of one million items, linear search might need a million comparisons, while binary search needs at most 20. This is the power of logarithmic time. However, if you only search a list once and it isn't sorted, the cost of sorting (O(n log n)) makes binary search more expensive overall. That's why linear search still has its place.

Beyond binary search, more advanced data structures like hash tables (Python dictionaries and sets) can achieve O(1) average-case lookups. As you progress in computer science, you'll learn when each approach is most appropriate. But every journey starts here — with the humble linear search.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

If you perform a linear search on a list of 200 elements and the target is at index 150, how many comparisons will the algorithm make before finding it? Why doesn't the algorithm skip ahead to index 150 directly?

Show answer

The algorithm will make 151 comparisons (checking indices 0 through 150 inclusive). Linear search cannot skip ahead because it has no way of knowing where the target might be — the list could be unsorted, so the target could be at any position. Each element must be checked in sequence. The algorithm has no information to guide it other than "check the next one."

Question 2: BASIC CALCULATION

Trace through the following code and determine the output:

def linear_search(lst, target):
    for i in range(len(lst)):
        if lst[i] == target:
            return i
    return -1

print(linear_search(["apple", "banana", "cherry", "date"], "cherry"))

Show answer

The output is 2. The function starts at index 0 and compares "apple" to "cherry" (no match). At index 1, it compares "banana" to "cherry" (no match). At index 2, it compares "cherry" to "cherry" — a match! The function returns 2. Note that linear search works with strings, not just numbers, because Python's == operator handles string comparison.

Question 3: INTERMEDIATE

Modify the linear search function so that it returns a list of all indices where the target appears, rather than just the first index. For example, find_all([5, 3, 7, 3, 9, 3], 3) should return [1, 3, 5]. Write the complete function.

Show answer

The key change is to collect matching indices in a list instead of returning immediately on the first match. Here is the solution:

def find_all(lst, target):
    result = []
    for i in range(len(lst)):
        if lst[i] == target:
            result.append(i)
    return result

We create an empty list result before the loop. Instead of return i inside the loop, we use result.append(i) to add each matching index. After the loop, we return the full list. If no matches are found, result will be an empty list []. Note that this version always checks every element — it cannot terminate early.

Question 4: APPLIED

A teacher stores student grades in a list: grades = [88, 92, 75, 100, 67, 92, 85]. Write a function first_failing(grades, passing_score) that uses linear search to find the index of the first grade below the passing score. If all grades are passing, return -1. Call it with passing_score = 70 and determine the output.

Show answer

The function modifies the standard linear search by changing the comparison condition:

def first_failing(grades, passing_score):
    for i in range(len(grades)):
        if grades[i] < passing_score:
            return i
    return -1

Calling first_failing(grades, 70) returns 4. The algorithm checks 88 (pass), 92 (pass), 75 (pass), 100 (pass), then reaches 67 at index 4, which is below 70. This demonstrates that linear search isn't limited to exact equality — you can adapt the condition to search for the first element meeting any criterion.

Question 5: CRITICAL THINKING

Suppose you have a sorted list of 10,000 numbers and you need to search for 500 different target values. Would you use linear search for each target, or would you sort the list and use binary search? Justify your answer by estimating the total number of comparisons for each strategy.

Show answer

With linear search, each of the 500 searches could require up to 10,000 comparisons, giving a worst case of 500 × 10,000 = 5,000,000 comparisons. With binary search, the list is already sorted, so no sorting cost is needed. Each binary search requires at most log₂(10,000) ≈ 14 comparisons, so 500 searches need about 500 × 14 = 7,000 comparisons. Binary search is about 700 times more efficient here. The lesson: when you need to search the same sorted list many times, binary search saves enormous amounts of work. Linear search would only be preferable if the list were very small or if you were only doing a single search on unsorted data.

SUMMARY

Summary

Linear search is the most straightforward searching algorithm: it starts at the beginning of a list and checks each element sequentially until it finds the target value or reaches the end. It returns the index of the match or a sentinel value like -1 if the target is absent. Its time complexity is O(n) in the worst and average cases, with O(1) space complexity.

The algorithm's greatest strengths are its simplicity and flexibility — it works on unsorted data and any data type supporting equality comparison. For large datasets or repeated searches, more efficient algorithms like binary search (O(log n) on sorted data) or hash-based lookups (O(1) average) should be considered. Understanding linear search is the essential first step in mastering algorithm design and complexity analysis.