Linear search

What you will be able to do

After this lesson you can

• search a list item by item, and say what the search gives back,
• count the checks that a search needs,
• change the search to find all the positions, or the first item that passes a test, and
• use index and in when they are enough.

Looking for something

You lose a card in a pile. The simplest way to find it: look at the cards one by one. This is linear search. You do not need the pile to be in any order.

Predict first. Where is the number 7? How many items does the loop look at? Then run it.

The loop looks at the positions 0, 1 and 2. The item at position 2 is 7, so it says so, and break leaves the loop. It did not need to look at the last two items. The break is what makes the search stop early.

As a function

A search is a good job for a function: the list and the target go in, and the answer comes out.

Python does a linear search for you: marks.index(90) gives the position (and a ValueError if it is missing), and 90 in marks gives True or False. Use them when you only need the answer. Write your own loop when you need to count the checks, or when the test is more than "equals".

All the positions, and the first that passes a test

A search can ask different questions. Here are two.

On average, a target that is there needs about half the list. A missing target always needs every check.

What linear search is good for

• It works on any list, sorted or not.
• It is easy to write and easy to get right.
• It is fast enough for a short list. For ten items, nobody cares.
• It is slow for a very long list, because the work grows with the length. We study that in the next lessons.

Common mistakes

• Returning inside the loop at the wrong indent. If return -1 is inside the loop, the function gives up after the first item.
• Using -1 as a position without checking. items[-1] is the last item.
• Using index for a missing target. A ValueError. Ask with in first, or use your own function.
• Forgetting break or return. The loop goes on although the target was found.
• Counting positions from 1. Positions start at 0.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

1. Warm-up. Open the problem Where is it? and the problem How many checks?
2. Build. Open the lab Search by hand. You write the search function, and the checker tries it on many lists.
3. Stretch. Open the problem First above a limit and change the function so that it finds the last position instead.

Remember these

• Linear search checks the items one by one. It works on any list.
• A search function gives back a position, and -1 when the target is not there.
• The worst case is n checks for n items.
• index() and in search a list for you.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. How many checks does linear search need to find the last item of 10 items?

2. What does a search function often give back when it finds nothing?

3. What does find_all([4, 7, 2, 7], 7) give?