AP® Computer Science Principles · Big Idea 3 · Topic 3.10
Linear Search
Linear search checks items one at a time, in order, from the start of a list until it finds the target or runs out of items. Its worst case on a list of n items is n comparisons.
Linear search is the brute-force way to find something: start at the first item, compare it to what you want, and if it does not match, move to the next item. Keep going until you find a match or reach the end of the list. It makes no assumptions about the list's order, which is exactly why it has to be so plodding. If the list is not sorted, there is no way to guess where the target might be, so nothing is lost by this item-by-item sweep, but nothing is gained either.
The number of comparisons depends entirely on where the target sits. Best case, it is the very first item: one comparison and done. Worst case, it is the last item, or not in the list at all, forcing a check of every single entry. On a 200 item list, that worst case is 200 comparisons. A single quick run that happens to match early tells you nothing about the algorithm in general, since the next search might need to check all the way to the end. Judging an algorithm's speed means looking at its worst case, not one lucky trial.
Linear search sits next to sorting and binary search in the course's arc on efficiency. Because linear search does not need a sorted list, it is the fallback whenever data has no useful order. But once a list is sorted, binary search can find a target in far fewer steps by repeatedly cutting the search space in half, which sets up the contrast between algorithms whose worst case scales with the whole list and ones that scale with its logarithm.
Key terms
- linear search
- An algorithm that checks each item in a list in order until it finds the target or reaches the end.
- worst case
- The scenario requiring the most steps, used to describe an algorithm's slowest possible performance.
- comparison
- A single check of whether one list item equals the target being searched for.
- unsorted list
- A list with no particular order, which rules out shortcuts like skipping sections during search.
Watch it explained
- How it worksHow does linear search walk a list in order and stop the moment it finds a match?
- Worked exampleTrace a linear search for 13 in the list 5, 9, 13, 2, 7 and count the comparisons.
- Worked exampleFind the worst case number of comparisons a linear search needs on a 200 item list.
- Common mistakeWhy isn't finding a match on the very first comparison proof that linear search runs fast in general?
- Going furtherWhat happens to the average number of checks when the target is not in the list at all?
Check yourself
End of topic.