Computer Science · Class 11 · Lists Revisited

ProgramsSearching⏱️ 15 min read

Searching a List

Looking for something in a list, one item at a time, is called linear search — and it is the algorithm every exam asks you to write. Two decisions shape all five programs here: whether to stop when you find it, and what to do when you get to the end and never did.

1Program 1 — linear search, with the position

📋 The problem

Ask for a number and say where it is in the list — or that it is not there at all.

linear_search.py

# search a list, and say so when the value is not there

numbers = [45, 88, 12, 91, 67]
wanted = int(input('Which number are you looking for? '))

for i in range(len(numbers)):
    if numbers[i] == wanted:
        print(wanted, 'found at position', i)
        break
else:
    print(wanted, 'is not in the list')

Output

Which number are you looking for? 12
12 found at position 2

linear_search.py — a number that is not there

Output

Which number are you looking for? 50
50 is not in the list

for i in range(len(numbers)):

The index form, because the answer IS the position. A loop over the items would find the value and have nothing to report about where it was.

break

Stop the moment it is found. On a list of five that saves nothing; on a list of fifty thousand it is the difference between an answer and a wait.

else:

Lined up with the for, not the if. A loop's else runs only when the loop was never broken — which is exactly what 'we looked at everything and it was not there' means.

Key Takeaway

Without the else, a failed search says nothing at all. The loop just runs out and the program ends in silence, which a user reads as a crash. Every search program needs an answer for the case where the thing is not there — for…else is the tidy way to write it, and a flag variable set before the loop is the other.

Python answers both questions in one call each: wanted in numbers is True or False, and numbers.index(wanted) gives the position — but index() raises ValueError when the value is missing, so it needs the in check first anyway.

2Program 2 — every position, not just the first

📋 The problem

A value may appear more than once. Report all of its positions.

all_positions.py

# every position a value appears at

numbers = [4, 7, 4, 2, 4, 9]
wanted = 4
found = False

for i in range(len(numbers)):
    if numbers[i] == wanted:
        print(wanted, 'at position', i)
        found = True

if not found:
    print(wanted, 'is not in the list')

Output

4 at position 0
4 at position 2
4 at position 4

Watch Out

No break here — and so no for…else either. The loop must run to the end, so its else would fire on every single run, found or not. When a search cannot stop early, the flag variable is the tool: set found to True beside the printing, and test it afterwards.

numbers.index(4) is no help at all here: it gives 2 and stops, and there is no built-in that hands back every position. This is the first program on the page a method cannot replace.

3Program 3 — what two lists have in common

📋 The problem

Given two lists, build a third holding the items that appear in both.

common_items.py

# the items two lists have in common

first = [3, 8, 12, 20, 25]
second = [5, 12, 20, 31]
common = []

for a in first:
    for b in second:
        if a == b:
            common.append(a)

print('Common items:', common)

Output

Common items: [12, 20]

A loop inside a loop, and the reason is worth saying: every item of the first list has to be compared with every item of the second, which is 5 × 4 = 20 comparisons. The inner loop runs completely on each round of the outer — the fact the nested-loops lesson exists for.

Tip

in turns the inner loop into one word. for a in first: if a in second: common.append(a) does the same job, because in is itself a search. Write the nested version when the question says “without using in”, and know that the shorter one is doing exactly the same work underneath.

Watch Out

Repeats come out repeated. If 12 appeared twice in the first list, it would be appended twice. Guarding with if a == b and a not in common: is the usual fix, and it is the same trick as removing duplicates on the next page.

4Program 4 — is there any bad reading at all?

📋 The problem

A list holds sensor readings. Say whether any of them is negative — the answer is one word, not a list of positions.

any_bad.py

# does the list hold any negative number at all?

readings = [23, 27, 25, 29, 31]
has_negative = False

for r in readings:
    if r < 0:
        has_negative = True
        break

if has_negative:
    print('There is a bad reading in the list')
else:
    print('Every reading is fine')

Output

Every reading is fine

any_bad.py — with readings = [23, 27, -1, 29]

Output

There is a bad reading in the list

Key Takeaway

“Is there any?” starts at False; “are they all?” starts at True. One counter-example settles either question, and the flag is never set back — once a negative has been seen, nothing later can un-see it. The break is optional and worth having: there is nothing left to learn after the first one.

5Program 5 — where does the order first break?

📋 The problem

Say whether a list is sorted, and if not, report the first place it goes wrong.

check_order.py

# is the list in order, and where does it first go wrong?

numbers = [3, 8, 12, 9, 20]

for i in range(len(numbers) - 1):
    if numbers[i] > numbers[i + 1]:
        print('Out of order at position', i)
        print(numbers[i], 'comes before', numbers[i + 1])
        break
else:
    print('The list is in order')

Output

Out of order at position 2
12 comes before 9

The neighbour comparison from the traversal page, with a break and a for…else wrapped round it — so the program reports the first fault rather than every fault, and says so cleanly when there is none. range(len(numbers) - 1) because the body reaches forward to numbers[i + 1].

check_order.py

numbers = [3, 8, 12, 9, 20]

for i in range(len(numbers) - 1):
    if numbers[i] > numbers[i + 1]:
        print('Out of order at position', i)
        print(numbers[i], 'comes before', numbers[i + 1])
        break
else:
    print('The list is in order')

numbers = [3, 8, 12, 9, 20]

for i in range(len(numbers) - 1):
    if numbers[i] > numbers[i + 1]:
        print('Out of order at position', i)
        print(numbers[i], 'comes before', numbers[i + 1])
        break
else:
    print('The list is in order')

6Recap

Linear search: stop when you find it

break the moment the answer is settled. A search for EVERY occurrence is the exception — it must run to the end.

for…else needs a break to mean anything

It runs when the loop was never broken. In a loop with no break it fires every time and reports 'not found' after finding things.

No break? Use a flag

found = False before the loop, True beside the printing, tested afterwards. It is what for…else is a shorthand for.

Two lists means two loops

Every item against every item — or the word in, which is the same search written shorter.

✍️ Now write these yourself

1
Search a list of names for one the user types.
Hint · Program 1 with strings. Compare with ==, and decide whether capitals should matter.
2
Count how many items two lists have in common, without building a third list.
Hint · A counter instead of the append() — and beware of counting a repeat twice.
3
Report the position of the last occurrence of a value.
Hint · No break; keep overwriting a variable and whatever survives is the last one.
4
Say whether a list is in descending order.
Hint · Program 5 with the comparison turned round. Decide what equal neighbours should mean before you write it.
5
Find the items that are in the first list but not in the second.
Hint · if a not in second: — and try writing it with a nested loop and a flag as well.

Quick Check

A search loop has no break, and a for…else after it. What does the else do?

Quick Check

Why does the 'every position' program use a flag rather than for…else?

Quick Check

Two lists of 5 and 4 items are compared with a nested loop. How many comparisons?

← Previous

🔢 Counting & Totals

Changing & Building Lists 🏗️