Problem Solving

Linear Search

Students inspect a row of wooden boxes one by one.

Linear Search definition

Linear search looks for a target by checking the items of a list one at a time.

In Spanish
búsqueda lineal
Topic
Algorithms and problem-solving

Linear Search in a picture

Linear Search diagramChecking 7, then 4, finds the target 4 on the second comparison.List: 7, 4, 9, 2Target: 4Compare 7 with 4No match, so continueCompare 4 with 4Match found at the second position
Checking 7, then 4, finds the target 4 on the second comparison.

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

Must the list be sorted?

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.