Linear Search

In Turkish: Doğrusal Arama
Pronunciation: LIN-ee-er SURCH

Updated October 3, 20262 min read

In short

Linear search finds a value by checking each element of a list one by one from the start until it finds a match or reaches the end, taking O(n) time.

What is linear search?

It is the simplest search there is: compare the first element with the target, then the second, and so on. If the target is at position 7, it takes 7 comparisons; if it isn't there at all, every element is checked. On average about half the list is examined when the value is present, which is still O(n), proportional to the list's length.

Its strength is that it needs nothing from the data. The list doesn't have to be sorted or indexed, it works on linked lists and streams that can only be read in order, and it can search by any condition, such as the first user older than 30. Built-in functions such as JavaScript's indexOf and find and Python's in operator on lists use linear search.

For small collections, linear search is often the fastest choice in practice: there is no setup, and scanning a few dozen items in a row is very friendly to CPU caches. Sorting first just to use binary search only pays off when the same data is searched many times.

A common misconception is that linear search is always a bad sign. It becomes a problem when it hides inside a loop, for example checking if item in big_list for each of thousands of items, which turns into O(n²). Replacing the list with a set or a hash map, which find items in O(1) on average, is usually the fix.

Key takeaways

Linear search checks elements one by one until it finds a match.
It takes O(n) time and needs no sorting or index.
It works on linked lists, streams and any search condition.
For small collections it is often the fastest option.
Inside loops it can become O(n²); use a set or hash map instead.

Example

Linear search and when to replace it (Python)python

def linear_search(items, target):
    for index, value in enumerate(items):
        if value == target:
            return index          # found: stop early
    return -1                     # checked everything, not there

print(linear_search([7, 3, 9, 4], 9))   # 2

# Slow: a linear search inside a loop → O(n * m)
banned = ["spam@x.com", "bot@y.com"]   # imagine thousands of entries
# clean = [u for u in users if u.email not in banned]

# Fast: a set makes each lookup O(1) on average
banned_set = set(banned)
# clean = [u for u in users if u.email not in banned_set]

Readers ask

What is the difference between linear search and binary search?

Linear search checks elements one by one and works on any list in O(n) time. Binary search repeatedly halves a sorted list and takes O(log n) time, but requires the data to be sorted first.

When is linear search a good choice?

For small or unsorted collections, data that can only be read in order, searches with complex conditions, or lists that are searched only once, where sorting or building an index would cost more.

What is the time complexity of linear search?

O(n) in the worst and average cases, because it may have to check every element. The best case is O(1), when the target is the first element.