Linear Search

Linear search scans a collection element by element until it finds the target, costing O(n) but requiring no ordering or preprocessing.

Check each in turn

Linear search, also called sequential search, examines each element from the start until it finds the target or reaches the end. It is the simplest possible search and the only option when the data is unordered or stored in a structure that cannot be indexed randomly, such as a linked list or a stream.

Cost

In the worst case the target is last or absent, so all n elements are examined, giving O(n). On average, for a present target uniformly distributed, about half the elements are checked, still O(n). The best case is O(1) when the target is first. No preprocessing and no extra memory are required.

• Best case: O(1) — target at the front
• Average and worst case: O(n)
• Extra space: O(1)
• Works on unsorted data and non-indexable structures

def linear_search(a, target):
    for i, x in enumerate(a):
        if x == target:
            return i
    return -1

The sentinel trick

A small optimisation places the target as a sentinel just past the end of the array, so the loop needs only one comparison per step, checking the value, instead of two, checking the value and the bounds. The bounds check happens once after the loop to distinguish a real find from hitting the sentinel. It does not change the O(n) bound but trims the constant factor.

When linear is the right choice

For small collections the simplicity of linear search beats the overhead of anything cleverer. It is also the natural fit when the data has no order to exploit, when you search only once so sorting first would not pay off, or when you need to find all matches rather than one. Once the same sorted data is searched many times, binary search or a hash table is far better, because their preprocessing cost is repaid across many queries.