Linear Search definition
Linear search looks for a target by checking the items of a list one at a time.
Linear Search in a picture
How it works
Start at the first position and compare each item with the target. Return the first match if the task asks for one, or report absence when the list ends. The method works even when the items are unordered. A list of n items can require n comparisons.
Worked examples
Search for 2 in [5, 9, 2]. How many comparisons?
Three, because 2 is the third item.
Search for 8 in [1, 3, 5]. What happens?
After three comparisons, report no match.
If the first item is the target, how many comparisons are needed?
One.
Common mistake
Stop only after a match or after all eligible items have been checked. An unmatched first item does not rule out later positions.
Quick check
What is the worst-case number of comparisons for n items?
Show answer
n.
What is another name for it?
Show answer
Sequential search.
Sources
Flashcard
Linear Search
Reveal the definition
Linear search looks for a target by checking the items of a list one at a time.
Effortless Math. “Linear Search.” Math Dictionary.
