Linear search

Why it costs this much

In the worst case it checks every item exactly once.

Code

def linear_search(items, target):
    for i, x in enumerate(items):    # up to n checks
        if x == target:
            return i                 # best case: first item, O(1)
    return -1

Common pitfalls

Repeating a linear search inside a loop makes O(n²). Build a set or dict first so each lookup is expected O(1).

Operation by operation

Linear search. Target equally likely to be anywhere, or absent. Works on unsorted data and any sequence, including linked lists.