"Is 27 in the list, and where?" is the oldest question a program asks about a collection of data. There are two answers: look at everything, or — when the data is sorted — look at almost nothing. This lesson is about both.
Linear search: look at everything
When the data has no particular order, there is no way round it: to find x
you look at the elements one by one, from the left, and stop at the first match.
That is linear search, and you have written it since Week 4 without the
name:
The same loop, with small changes, answers the other classic questions:
| Question | Change |
|---|---|
| the last occurrence | drop the break, so the last match overwrites pos — or scan from the right |
how many times does x occur | replace pos = i; break; by count++ |
| the first element with a property | replace a[i] == x by the property: a[i] > k, a[i] == a[i + 1] |
the first match inside a[l..r] | run i from l to r |
A bridge is tested by n vehicles in turn. Each produces a stress level; the bridge is damaged by the first vehicle whose level is strictly above k. Print that vehicle's number, or -1 if none is.
That is the loop with a[i] > k as the test and i + 1 printed. Linear search
takes up to n steps, and for a single question that is fine: 5·10⁶ elements
are looked at in well under a second. The trouble starts with
questions: 10⁵ queries on 10⁵ elements is 10¹⁰ steps.