Lesson 7.5

Linear search

Part 7: AlgorithmsReading, about 7 min3 exercises in this lesson, in Python2 exercises in this lesson, in Java

Java answers can't run on ExamSpine yet. You can still read Java, trace it, and put an answer's lines in order.

Linear search

By the end of this you will be able to write a linear search in Python and in Java that returns where a value is, or -1 when it is not there, and state its complexity with a reason.

How it is asked

Linear search is one of the few algorithms the course names, so expect to write it from memory. The new course has no past papers yet (the first exams are in May 2027), but expect three shapes:

Write a function (a method in Java) that returns the index of a value in a list or array, or -1 if it is missing.
Change it slightly: count the matches, find the first value over a limit, or return a true or false answer.
Trace it, or state its Big O and say why.

Our rubrics give a mark to each piece of the algorithm: the loop, the comparison, returning the index, and returning -1 at the right moment. That last one is the easiest to get wrong.

Key idea: A linear search checks each value in turn, from the start, and stops at the first match.

Watch it look

Here the search wants the first 7. Step through it and watch the arrow move along the list.

Step through it

scores = [12, 7, 19, 7, 3]

target = 7

position = -1

for i in range(len(scores)):

if scores[i] == target:

position = i

break

print(position)

Variables

Nothing yet. Press Next to run the first line.

Nothing has run yet.

Output

(nothing printed)

0/10

Two comparisons, and the search stops at index 1. The 7 at index 3 is never looked at.

The search gives back a position, not a value. You already know the value (it is the target), so the useful answer is where it is.

As a function

Most questions want a function. A return inside the loop ends the function at once, so it does the job of break.

def linear_search(values, target):
    for i in range(len(values)):
        if values[i] == target:
            return i
    return -1


print(linear_search([12, 7, 19, 7, 3], 7))
print(linear_search([12, 7, 19, 7, 3], 5))

public static int linearSearch(int[] values,
                               int target) {
    for (int i = 0; i < values.length; i++) {
        if (values[i] == target) {
            return i;
        }
    }
    return -1;
}

public static void main(String[] args) {
    int[] scores = {12, 7, 19, 7, 3};
    System.out.println(
        linearSearch(scores, 7));
    System.out.println(
        linearSearch(scores, 5));
}

Both print 1, then -1. The return -1 sits after the loop, so it only runs when every value has been checked and none matched.

Key idea: Return -1 only after the loop has looked at every value.

The early -1

Here is the easiest slip to make. The else looks tidy, but it is in the wrong place.

def linear_search(values, target):
    for i in range(len(values)):
        if values[i] == target:
            return i
        else:
            return -1
    return -1

Quick check

What does this version return for linear_search([12, 7, 19], 7)?

This version only ever looks at the first value. It still gives the right answer when the target is first or missing, which is why it can pass a quick test and still lose marks.

How it is marked

An exam-style question of our own, marked a point at a time. Switch to the second script for the early -1.

How it is marked

Construct a function linear_search(values, target) that returns the index of the first occurrence of target in the list values, or -1 if it is not there. [4]

[4]

for i in range(len(values)):[1]
A loop that can reach every index.

So far 1 of 4

Three of four: one line in the wrong place costs the mark for the whole "not found" case.

The same marks go to a Java answer, or to a version with a while loop and a found flag. Either works, as long as it stops at the first match and only says "not found" once it has looked everywhere.

How fast it is

For a list of n values, the best case is one comparison: the target is first. The worst case is n comparisons: the target is last, or missing. So a linear search is O(n). Double the list and, in the worst case, you double the work.

Quick check

A linear search takes at most 2 milliseconds on a list of 10000 values. Roughly how long, at most, on a list of 40000?

A linear search has one big strength: it works on any list, sorted or not. The next lesson's search is much faster, but only on sorted data.

Ready-made searches

Python's target in values and values.index(target) both do a linear search for you, so they are O(n) too. Note that index does not give -1 when the value is missing: it raises a ValueError, which stops the program unless it is caught. A question that says "construct" or "write" a search wants the loop, so write it out.

Now try it yourself on the questions below.

Exercise 7.5.17.5.1 · Write itWhere is it?

Write a function that does a linear search: it looks through a list (an array in Java) of whole numbers, from the start, for a target value.

Return the index of the target, counting from 0.
If the target is in the list more than once, return the index of the first one.
If the target is not in the list, return -1.
The list can be empty.

Do not use a ready-made search such as values.index(target) (indexOf in Java): write the loop. Only the value your function returns is checked.

def position_of(values: list[int], target: int) -> int

You cannot use these in this question:

.index()
import operator

This question is about writing the linear search yourself, so ready-made searches are not allowed.

Examples

Your function is tested on 11 cases: the 4 examples below, and 7 hidden ones that check the rules above.

position_of([4, 8, 15, 16], 15) should return 2: the target is in the middle (rule 1)
position_of([4, 8, 15, 16], 5) should return -1: the target is not there (rule 3)
position_of([3, 9, 3, 9], 9) should return 1: the target is there twice: the first one counts (rule 2)
position_of([9, 1, 2], 2) should return 2: the target is the last value (rule 1)

public static int positionOf(int[] values, int target)

Running Java here comes later. You can put this answer's lines in order instead. You can still write your Java answer (it stays while this page is open) and compare it with our worked solution. Or try this exercise in Python.Checking whether Java answers can run here.

You cannot use these in this question:

Arrays.asList()
Arrays.binarySearch()
.indexOf()
.contains()

This question is about writing the linear search yourself, so ready-made searches are not allowed.

Examples

Your function is tested on 11 cases: the 4 examples below, and 7 hidden ones that check the rules above.

positionOf(new int[]{4, 8, 15, 16}, 15) should return 2: the target is in the middle (rule 1)
positionOf(new int[]{4, 8, 15, 16}, 5) should return -1: the target is not there (rule 3)
positionOf(new int[]{3, 9, 3, 9}, 9) should return 1: the target is there twice: the first one counts (rule 2)
positionOf(new int[]{9, 1, 2}, 2) should return 2: the target is the last value (rule 1)

solution.pySolution.java

def position_of(values: list[int], target: int) -> int:
    # your code here
    pass

Exercise 7.5.27.5.2 · Write itFirst hot day

A weather station keeps one temperature a day, in whole degrees, in a list (an array in Java). Day 0 is the first day. Write a function that finds the first day that was hotter than a limit.

Return the first day whose temperature is greater than limit.
A temperature equal to the limit is not hotter than it.
If no day was hotter, return -1.
The list can be empty, and temperatures can be below zero.

Only the value your function returns is checked.

def first_day_over(temps: list[int], limit: int) -> int

Examples

Your function is tested on 9 cases: the 3 examples below, and 6 hidden ones that check the rules above.

first_day_over([21, 24, 31, 28, 33], 30) should return 2: day 2 is the first day over 30 (rule 1)
first_day_over([21, 24, 19], 30) should return -1: no day is over the limit (rule 3)
first_day_over([30, 30, 31], 30) should return 2: days equal to the limit do not count (rule 2)

public static int firstDayOver(int[] temps, int limit)

Examples

Your function is tested on 9 cases: the 3 examples below, and 6 hidden ones that check the rules above.

firstDayOver(new int[]{21, 24, 31, 28, 33}, 30) should return 2: day 2 is the first day over 30 (rule 1)
firstDayOver(new int[]{21, 24, 19}, 30) should return -1: no day is over the limit (rule 3)
firstDayOver(new int[]{30, 30, 31}, 30) should return 2: days equal to the limit do not count (rule 2)

solution.pySolution.java

def first_day_over(temps: list[int], limit: int) -> int:
    # your code here
    pass

Exercise 7.5.3 · Trace itTrace: linear search

Complete the trace table for this Python code. The loop stops once found is True, or once no values are left. Then answer the question below the table. [4]

Line 1: values = [6, 2, 9, 4]1values = [6, 2, 9, 4]
Line 2: target = 92target = 9
Line 3: i = 03i = 0
Line 4: found = False4found = False
Line 5: while i < len(values) and not found:5while i < len(values) and not found:
Line 6, indented 1 level: if values[i] == target:6    if values[i] == target:
Line 7, indented 2 levels: found = True7        found = True
Line 8, indented 1 level: else:8    else:
Line 9, indented 2 levels: i = i + 19        i = i + 1
Line 10: print(i)10print(i)

Fill in one row each time a line changes i or found, or prints something. The table already has the right number of rows. In each row, write only what that line changes; you can leave the other cells empty or copy their values down. Write values the way Python shows them: 3 and 3.0 are different, and text goes in quotes. In the output column, write exactly what appears on screen, with no quotes around it.

Row	i	found	output
1
2
3
4
5
6

How many times was a value in the list compared with the target?

Report a problem with this page