Repeating Until It Is Done
Searching a list
Follow a search that goes through a list from the front until it finds what it wants, and work out where it stops and how many values it had to look at.
A computer cannot glance at a list and see whether something is in it. It has to look at the values one at a time, starting at the front, and either find what it wants or run out of list. That is a search, and it is the plainest algorithm there is — which is exactly why it is worth counting carefully. What matters about it is not that it works. It is how much work it does.
Where it stops, and how much it looked at
A search that stops the moment it finds what it wants stops at the position of the first match and never looks past it, so a value appearing twice is only ever found at the earlier of the two. If it stops at position p, it has looked at p + 1 values: one more than the position, because positions are counted from nought while looks are counted from one. And if what it wants is not in the list at all, it looks at every single value, however long the list is. There is no way round that last one — a value it has not looked at could always have been the one it wanted.
Worked example
What does this program print, and where does the search stop?
values = [4, 5, 9, 5]
i = 0
while values[i] != 9:
print(i)
i = i + 1i holds 0, so the condition looks at values[0], which is 4. That is not 9, so the body runs: it prints 0 and moves i on to 1.
The condition reads a value out of the list every time it is checked. The position is what changes; the list itself is left alone throughout.
Try it together
No program this time. A search that stops as soon as it finds what it wants is run on a list of 20 values.
Three runs of the same search, and each one is answered by counting rather than by tracing.
1.On the first run it finds what it wants at position 8. How many values did it look at?
Have a go
Have a go on your own. What does this program print?
values = [2, 7, 3, 7]
i = 0
while values[i] != 3:
i = i + 1
print(i)Ready to practise?
Eight questions on what you have just read. Nothing is timed, and you can play as many times as you like.