Linear search: one item at a time

Someone hands you a shuffled deck and asks for the queen of hearts. The deck has no order, so the card on top says nothing about the rest, and all you can do is turn cards over one at a time until she appears. She might be the first card. She might be the last, or missing altogether, and you can only say she is missing once you have turned all 52. If she is in the deck, you turn 26.5 cards on average.

That is linear search, also called sequential search: check each item in turn until one matches or the items run out. It is the baseline every faster search is measured against, and often the right choice, because it asks nothing of the data: no order, no way to jump to the middle, not even knowing in advance how many items there are.

target

The value being searched for. The search reports the index of the first element equal to it, or −1 when no element is.

probe

One comparison of an element with the target. Probes are the work a search does, and the visualiser counts them.

hit and miss

A hit finds the target and stops there. A miss reaches the end without finding it, so it has compared every element.

best, average and worst case

The fewest probes any input of size n needs, the mean over every place the target could be, and the most any input needs.

sequential access

Reading items in order, one after another, with no way to jump ahead: all a linked list or a stream of data offers.

This array holds 23, 7, 61, 42, 15, 88, 34 and 9, in no particular order, and the target is 15. Step through and watch the bracket of positions that could still hold 15: every probe that fails takes one position off its left end.

The whole algorithm is one loop and two returns. A failed probe tells the search only that this position does not hold the target: with no order, A[3] = 42 says nothing about A[4], so there is nothing to skip. A hit at index k therefore costs k + 1 probes, one for each of positions 0 to k: 15, at index 4, took 5. A miss costs all n, because the search can only report the target absent once it has ruled out every position.

So where the target sits decides the cost. In the best case it is at index 0: one probe. In the worst it is last, or missing: n probes. If it is always there and equally likely to be anywhere, the costs 1, 2, …, n happen equally often, and their average is (n + 1)/2, about half the list. For the deck that is (52 + 1)/2 = 26.5 cards.

This array holds 47 twice, at positions 5 and 7, and 47 is the target. Before you start, decide which position the search will report and how many probes it will make. At each probe, say whether it is the target before the next step plays, then check your count at the end.

Here it is as a function. It returns the index of the first match, or −1, and counts its comparisons in checks so it can print what each search cost. The program searches five scores twice: for a value that is there, and for one that is not.

def linear_search(items, target):
    checks = 0
    for i in range(len(items)):
        checks += 1
        if items[i] == target:
            print('index ' + str(i) + ' after ' + str(checks) + ' checks')
            return i
    print('index -1 after ' + str(checks) + ' checks')
    return -1

scores = [31, 8, 57, 14, 42]
linear_search(scores, 14)
linear_search(scores, 20)

The loop only ever asks for the next item. It never jumps, ignores the order, and written as for x in items needs neither indices nor the length. So linear search works where binary search can't, or gains nothing: on an unsorted list, on a linked list, where reaching the middle means walking there anyway, and on a stream, such as readings from a sensor, where each item is seen once, in order.

The predict run showed one more property: the search stops at the first match, so the 47 at position 7 was never compared.

Order changes one thing. If the list is sorted, a miss can stop as soon as an item passes the target, since everything after it is bigger still. The visualiser runs the plain search, which ignores the order, so you can count what an early stop would save.

The early stop helps misses, not the growth: a target bigger than every item still checks them all. To get real value from sorted order, a search has to use it to skip. That is binary search: about log₂ n probes instead of n, 20 instead of a million.

So an O(n) search is often the right one: for data searched once or a few times, for small lists, where its simple loop is often as fast as binary search, for jobs that want every match, and for data that can only be read in order. It loses when the same data is searched again and again. Then sort once and binary search, O(log n) a lookup, or use a hash table, O(1) a lookup on average.

• Linear search checks each item in turn and stops at the first match: a hit at index k costs k + 1 probes, a miss all n.
• One probe at best, (n + 1)/2 on average for a hit, n at worst: O(n) time and O(1) extra memory.
• It needs only the next item, so unsorted arrays, linked lists and streams all work.
• It reports the first copy; counting or collecting every match scans all n.
• On sorted data a miss can stop once the items pass the target, but the worst case is still n.
• Sorting first costs O(n log n): scan for one search or a few, and for many, sort and binary search or use a hash table.
• Next: binary search, about log₂ n probes on sorted data, and hash tables, O(1) lookups on average. Practise with Spot a Repeated Number and Two Sum, where a fresh scan for every number costs about n²/2 comparisons and a hash set or map needs one pass, then Find a Number in a Sorted List. Or try your own arrays on the linear search visualiser.