Linear Search
Looking for a value by checking items one after another until it is found or the collection runs out, and counting the checks that takes in the best and worst case.
What a learner can do afterwards
- Write a loop that reports the position of a value, or reports that it is absent
- Say how many comparisons the worst case needs for a list of a given length
- Explain why this search works on data in any order
1 · Read
Imagine scanning a class list for one name. Linear search does the same: it checks items one after another from the front, asking if each one equals the target. It stops with the seat number on a match, or reports absent at the end.
Take searchList with 3, 37, 45, 57, 93 and 120, hunting 45. Checks answer no, no, then yes at the third item, so it hands back seat 3. Hunting 99 would check all six and hand back -1.
The worst case checks every item, so twice the list means twice the worst time. On a nonempty list, best case finds the target first, and average lands mid-list. For 30 names the hunt may need 30 checks.
No sorting, no setup: on jumbled data, short lists or one-off hunts, the simple scan wins. Pay for sorting only when many searches follow.
Check from the front until match or end, count the checks, and expect the worst to grow with the list.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.