Grade by Grade
A. Programming Concepts and Skills · Algorithm Design and Analysis

Linear Search in Depth: Records, Variations and Analysis

A3.2 C2.2 C2.1About 70 minutes
Learning goals
  • I can write linear searches that return the first match, the last match or every match.
  • I can search an array of records by one field, such as a name or an ID.
  • I can count the comparisons a linear search makes in the best, worst and average case.
  • I can state the precondition and postcondition of a linear search.

Words to know

linear (sequential) search
Checking elements one at a time, from one end, until the target is found or every element has been checked.
key
The field of a record that a search compares with the target, such as a student number.
successful / unsuccessful search
A search that finds the target / one that ends without finding it.
predicate
A function that returns True or False for an element; a search can look for the first element where the predicate is True.
average case (linear search)
If the target is present and equally likely to be at each of the n positions, the average number of comparisons is (n + 1) ÷ 2.

Lost mitten at the community centre

The lost-and-found bin at a community centre is a jumble. To find your red mitten you take items out one at a time until you find it, or until the bin is empty. There is no smarter way, because the bin is in no order. That is linear search, and it is the only general way to search unsorted data.

In ICS3U you wrote a linear search that returned the index of a number or −1. In this lesson you extend it to real data (arrays of records), to useful variations (last match, all matches, matching a condition), and you analyse it exactly: how many comparisons does it make?

The contract

  • Precondition: a is a list (any order) whose elements can be compared with target using ==.
  • Postcondition: returns the smallest index i with a[i] == target, or −1 if there is no such index; a is unchanged.

Notice what the precondition does not say: the list does not need to be sorted. That is linear search's big advantage.

def linear_search(a, target):
"""Return (index of first match or -1, comparisons made)."""
comparisons = 0
for i in range(len(a)):
comparisons += 1
if a[i] == target:
return i, comparisons
return -1, comparisons
a = [31, 8, 47, 15, 62, 23, 90, 54]
for t in [31, 23, 54, 40]:
print(t, linear_search(a, t))

Output, one line each: 31 (0, 1), 23 (5, 6), 54 (7, 8), 40 (-1, 8). The counter is only there for analysis; a real search returns just the index.

Searching for 23 in an unsorted list31081472153624235906547#1#2#3#4#5#6aComparisons are numbered above the cells. 23 is found at index 5 after 6 comparisons.Indexes 6 and 7 are never looked at. A missing target would need all 8 comparisons.
A linear search compares the target with each element in order. Finding the element at index k takes k + 1 comparisons.

Exact analysis

Count comparisons of an element with the target; that is the basic operation.

  • Best case: the target is at index 0. 1 comparison, O(1).
  • Worst case: the target is at the last index, or not there at all. n comparisons, O(n).
  • Average case (target present): if the target is equally likely to be at any of the n positions, the number of comparisons is 1, 2, 3, …, n with equal chance. The average is

(1 + 2 + … + n) ÷ n = [n(n + 1) ÷ 2] ÷ n = (n + 1) ÷ 2.

So on average a successful linear search checks about half the list. That is still O(n): double the list and the average work doubles.

  • Unsuccessful search: always n comparisons, because you cannot be sure the target is missing until you have checked everything.
0246801234567average 4.5index of the targetcomparisons
For n = 8, a target at index k needs k + 1 comparisons. If every position is equally likely, the average is (1 + 2 + … + 8) ÷ 8 = 36 ÷ 8 = 4.5, which is (n + 1) ÷ 2.
def comparisons_to_find(a, target):
for i in range(len(a)):
if a[i] == target:
return i + 1
return len(a)
a = list(range(100, 200)) # 100 different values
counts = [comparisons_to_find(a, t) for t in a]
print(len(a), sum(counts) / len(counts))

Output: 100 50.5. An experiment that searches for every element once. The average, 50.5, matches (n + 1) ÷ 2 for n = 100.

Searching an array of records

Real data is rarely a list of plain numbers. More often it is a list of records, and you search on one field, the key. Here each record is a dictionary; with the dataclass records from One-Dimensional Arrays of Records (in Data Types, Files and Expressions) you would write records[i].id instead of records[i]["id"], and the algorithm is the same.

skiers = [
{"id": 4102, "name": "Maya", "club": "Blue Mountain"},
{"id": 3877, "name": "Liam", "club": "Mont Tremblant"},
{"id": 5120, "name": "Aanya", "club": "Blue Mountain"},
{"id": 2954, "name": "Thomas", "club": "Whistler"},
]
def find_by_id(records, wanted_id):
"""Return the index of the record with this id, or -1."""
for i in range(len(records)):
if records[i]["id"] == wanted_id:
return i
return -1
def find_all(records, field, value):
"""Return a list of indexes of every record whose field equals value."""
matches = []
for i in range(len(records)):
if records[i][field] == value:
matches.append(i)
return matches
i = find_by_id(skiers, 5120)
print(skiers[i]["name"])
print(find_all(skiers, "club", "Blue Mountain"))
print(find_by_id(skiers, 1111))

Output, one line each: Aanya, [0, 2], -1. Returning an index (not the record) lets the caller read, change or delete that record. find_all must check every record, so it always makes n comparisons.

More variations

  • Last match: loop backwards, for i in range(len(a) - 1, -1, -1):, and return the first match you meet.
  • Case-insensitive text search: compare a[i].lower() == target.lower(), so "Whistler" matches "whistler".
  • Search by a condition (predicate): pass a function that says whether an element qualifies. This one finds the first temperature below freezing:
def find_first(a, test):
"""Return the index of the first element x where test(x) is True, or -1."""
for i in range(len(a)):
if test(a[i]):
return i
return -1
def below_zero(t):
return t < 0
highs = [12, 7, 3, -2, 1, -6] # daily highs in November, in degrees C
print(find_first(highs, below_zero))
print(find_first(highs, lambda t: t < -10))

Output, one line each: 3, -1. The second call uses a lambda, a one-line unnamed function. No high is below −10, so it returns −1.

Worked example

Early exit on sorted data

A list of 1000 student numbers is sorted in ascending order. A linear search for a number that is not in the list normally checks all 1000. How can the sorted order help, and what is the new precondition?

  1. In a sorted list, once you reach an element bigger than the target, every later element is bigger too, so the target cannot appear later.
  2. Add elif a[i] > target: return -1 inside the loop, after the equality test.
  3. New precondition: a is sorted in ascending order. (Without it, the early exit can miss a match, as you saw with count_sorted in the worked example of Specifying Algorithms: Preconditions, Postconditions and Loop Invariants.)
  4. Effect: an unsuccessful search now stops at the first bigger element: on average about half the list instead of all of it. It is still O(n) in the worst case (a target bigger than everything).
  5. This is a small gain. The next lesson shows how sorted data allows a much faster search.

Stop as soon as a[i] > target and return −1. It needs the precondition "sorted ascending" and roughly halves the work of an unsuccessful search, but the worst case is still n comparisons, O(n).

Do not over-engineer

Python's a.index(x) (which raises ValueError if x is missing) and x in a are linear searches written in fast C code. Use them in everyday programs. Write the algorithm yourself when you need something they do not do (records, last match, conditions, counting comparisons), and in this course, where you must show you can create the algorithm (A3.2).

Just for fun

Linear search's motto: "It's always in the last place you look."

That is actually true: you stop looking once you find it. (On average, though, linear search only has to look through half the list.)

Hands-on activity

The lost-and-found experiment

You need: 10 small household objects (a spoon, a sock, a key, an eraser, …), a cloth bag or pillowcase, a partner, paper and a pencil, and a computer with Python.

  1. Put the objects in the bag. Your partner names one object. Take items out one at a time without looking inside until you find it. Record the number of items you took out (the number of comparisons). Put everything back and shake the bag.
  2. Repeat 20 times, with your partner choosing targets at random (for example by rolling a die twice or picking names out of a hat).
  3. Find the average number of comparisons. Theory says (n + 1) ÷ 2 = 5.5 for n = 10. How close were you?
  4. Now your partner names an object that is not in the bag (e.g. a mitten). How many items must you take out before you are sure? (All 10.)
  5. In Python, simulate the experiment 10 000 times with random.choice to pick a target and random.shuffle to mix the list, and print the average comparisons. It should come out very close to 5.5.

What to look for: 20 real trials will be close to 5.5 but not exact; the 10 000-trial simulation should be within about 0.1.

Your turn

1

A linear search runs on a list of 40 elements. How many comparisons in the best case, the worst case, and on average for a successful search?

2

Why can linear search work on unsorted data while early exit cannot?

3

Write a function find_last(a, target) that returns the index of the last match, or −1.

4

What does find_all(skiers, "club", "Whistler") return for the lesson's data?

5

Why does find_all always make n comparisons, even when the first record matches?

6

A program searches a list of 1 000 000 postal codes, and 30% of searches are for codes that are not in the list. Which kind of search costs the most, and how many comparisons does it make?

More practice: warm-up

1

What does linear search return in the lesson when the target is missing?

2

What is the Big-O of linear search in the worst case?

3

What is the field you search on in a list of records called?

4

For a = [5, 3, 5, 9], what do a first-match search and a last-match search for 5 return?

5

What is (n + 1) ÷ 2 for n = 9, and what does it mean for linear search?

More practice: on your own

1

Predict the output:

names = ["Ava", "ben", "Chloé", "BEN"]

hits = []

for i in range(len(names)):

    if names[i].lower() == "ben":

        hits.append(i)

print(hits)

2

Write count_matches(a, target) without using a.count, and give its exact number of comparisons for a list of length n.

3

A list has 12 elements and the target is at index 7. How many comparisons does a forward search make? A backward (last-match) search?

4

Use find_first from the lesson with a lambda to find the first even number in [7, 13, 4, 10]. What is returned?

5

A search with early exit runs on the sorted list [3, 8, 12, 19, 25, 31] with target 14. List the elements it compares and the result.

Challenge

1

If the target is present with probability ½ (and, when present, equally likely at each position), what is the expected number of comparisons for a linear search of n elements?

2

Sentinel search: put the target at the end of the list (a.append(target)), then loop while a[i] != target: i += 1 with no index check. Explain why the loop is safe, what the function must do afterwards, and why this can be slightly faster.

3

Self-organizing list: after each successful search, the found element is swapped one place toward the front. If one item is searched for far more often than the others, what happens over time, and how does it affect the average comparisons?

Check your understanding

Quiz

1.

What is the precondition of the basic linear search?

2.

How many comparisons does an unsuccessful linear search make on a list of n elements?

3.

For n = 99, what is the average number of comparisons for a successful linear search (every position equally likely)?

4.

Which loop header visits a list from the last index down to index 0?

5.

Why does find_all return a list of indexes rather than stopping at the first match?

6.

Early exit (stopping when an element is bigger than the target) changes linear search how?

For parents and teachers

Big idea: A3.2 asks students to create linear and binary search algorithms; this lesson takes linear search to Grade 12 depth (records, variations, predicates) and analyses it exactly, the first half of C2.2. Stating its contract continues C2.1.

How to help: The lost-and-found activity makes the (n + 1) ÷ 2 average concrete. Ask your teen to predict the average before the 20 trials, and to explain why a missing item always takes 10.

Common difficulties:

  • Putting return -1 inside the loop (in an else), which stops after the first element.
  • Off-by-one errors in backward loops: range(len(a) - 1, -1, -1) is correct; range(len(a) - 1, 0, -1) skips index 0.
  • Mixing up the record and its index.
  • Thinking the average case is n ÷ 2 exactly: it is (n + 1) ÷ 2, because positions are counted from 1 comparison, not 0.