Check every element until you find it. Simple, always correct, works on any list — and today you make it count its own work, which turns out to be the most important thing about it.
No reading — this page is the reading. Runestone doesn’t cover Unit 4 (search, efficiency, limits, simulation), so everything you need is right here.
Programs, Algorithms region. You’ve written traversals since 3.8. Today one of them gets a name, a purpose, and — for the first time — a step counter. The number it produces is the first data point of the unit.
Now the real question: what’s the most names they could ever be forced to check? That number — not the lucky case — is what computer scientists care about.
Linear search (also called sequential search) checks each element in order,
from the first, until it finds the target or runs out of list. It’s a traversal with an early exit
— the return from 3.13 finally earning its keep.
def linear_search(items, target): i = 0 while i < len(items): if items[i] == target: return i # found: stop now i = i + 1 return -1 # checked everything
PROCEDURE linearSearch(items, target) { i ← 1 REPEAT UNTIL (i > LENGTH(items)) { IF (items[i] = target) { RETURN (i) } i ← i + 1 } RETURN (-1) }
Hover or tap a line to light its twin. Both flips in one procedure:
line 2 starts at 0 in Python but 1 in AP, and line 3’s while i < len becomes
REPEAT UNTIL i > LENGTH — opposite conditions, same loop.
| Where the target is | Elements checked (list of n) | Name |
|---|---|---|
| First element | 1 | best case |
| Position k | k | — |
| Last element, or not in the list | n | worst case |
Pick a target and step through the search one check at a time. Then scale it up and build your first data table.
Search lists of different sizes for a value that isn’t there (guaranteed worst case). Each run adds a row. Copy these into your Lab 4.3 table.
Your teacher hands out the spec. Part 1 is linear search with a step counter — do it today. Parts 2–4 need binary search from 4.4. Keep your data table: 4.5 puts it next to the binary one.
Five questions. Watch the index flip on the pseudocode trace.
When you press Ctrl+F on a web page, your browser checks the page’s text from the top. For one page, that’s instant. Now imagine a search engine doing that to billions of pages every time anyone types a query — worst case, every page, every time.
That’s why search engines never search the web when you ask. They organize it ahead of time into an index, so the lookup is fast. Linear search is simple and always correct; at planet scale, simple stops being enough.
return.