Find it one by one
Search a list of test marks or shop prices for a number, checking one item at a time. Count the comparisons when the number is first, in the middle, last, or not in the list at all.
Core concept
Linear search compares the target with each item in order; it needs 1 comparison at best and as many as there are items at worst, or when the target is missing
Topic: Algorithms
How do you find your name in a register that is not in any order? You read the names one by one from the top until you reach yours. That is linear search, the simplest searching algorithm: A list of clear steps that solves a problem, like a recipe. All key words. The program compares the target with the item at index 0, then index 1, and so on. If an item matches, it stops and reports the index. If it reaches the end without a match, the target is not in the list. Linear search works on any list, sorted or not, but it can be slow: in a list of 8 items it may need 8 comparisons.
What you will learn
- Trace linear search one comparison at a time.
- Count the comparisons in the best case, a middle case and the worst case.
- Explain why a missing item needs a comparison with every item.
- Write the steps of linear search in order.
Before you start
- Know what a list and an index are.
Materials
- A notebook to record the comparisons
Equipment
- None
Procedure
- Search the test marks for 91 and count the comparisons.
- Search for 45, the first mark.
- Search for 50, which is not in the list.
- Answer the practice challenges.