Linear Search Best and Worst Cases

A linear search checks items one at a time from the start until it finds the target or runs out of items. How many comparisons it makes depends on where the target sits in the collection, or whether it is there at all.

Best case

The best case is the target sitting in the first position: the search compares it, they match, and it stops. That is one comparison, and no search that compares items can do better.

Searching the playlist ['Echoes', 'Mist', 'Orbit', 'Pulse', 'Drift'] for Echoes needs one comparison. Searching for Mist needs two, because Echoes is checked and rejected first, so position matters, not list size.

Worst case

The worst case happens in two situations:

• The target is the last item, so every other item is compared and rejected first.
• The target is absent, so every item is checked before the search can report that it is not there.

Either way the search makes as many comparisons as there are items. Saying “linear search always checks every item” is therefore wrong: it only does so in the worst case.

The comparisons needed for that playlist:

Stopping early in sorted data

If the collection is sorted, the search can stop before the end. In ascending order, once the current item is greater than the target, the target cannot appear later, so there is no need to keep looking. In descending order the rule flips: stop once the current item is less than the target.

Searching the sorted list [4, 9, 15, 22, 30, 41] for 18 compares 4, 9, 15 and then 22. Because 22 is bigger than 18 in an ascending list, you stop after four comparisons instead of six and report that 18 is not present. That early stop is not a match: it means the target's possible position has been passed.