Linear Search

Linear search checks items one by one until it finds the target or reaches the end. It is the simplest search algorithm.

Linear search is useful as a baseline because it shows what the algorithm does when it has no extra structure to exploit.

Core Idea

If the input is unsorted and no index or hash table is available, the algorithm may have to inspect each element. The worst case is that the target is absent or appears at the last position.

The time complexity is O(n). The extra space is usually O(1).

Python Example

def find_index(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1

The loop stops as soon as the target is found.

Common Confusions

Linear search is not bad by default. For small inputs, one pass is often enough and easier to trust than a more complex structure.

It is also not the same as checking membership with target in values, although Python may perform a linear search internally for lists.

When To Use It

Use linear search when the input is small, unsorted, or searched only once. If many searches are needed, sorting or a hash-based structure may be worth the extra setup.