Linear search in Python

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Which code correctly starts a linear search through the list scores?

A for i in range(scores):

B for i in range(len(scores)):

2. What does a linear search do?

A Jumps to the middle of the list and halves the search area each time

B Checks each item in order until it finds the target or reaches the end

3. A linear search finds the target at index 2. What should the function do next?

A return i straight away

B keep looping to the end of the list

4. Which value does a linear search commonly return when the target is NOT in the list?

A -1

B 0

5. Which comparison checks whether the current item matches the target?

A if names[i] == target:

B if names[i] = target:

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
1for i in range(len(items)):		ACompares the current item with the value being searched for
2if items[i] == target:		BLoops through every index of the list so each item can be checked in turn
3When the target is found, the search stops and gives back its position (index)		CUses = (assignment) instead of == (comparison), which causes a syntax error. It should be ==.
4If the loop finishes without finding the target, the search returns -1 to show it is not in the list		Dreturn -1 is inside the loop, so the search gives up after checking only the first item. It should be after the loop, not inside it.
5if items[i] = target:		Ereturn i
6for i in range(len(items)): if items[i] == target: return i return -1		Freturn -1

Definitions

linear search

Fill in the Blanks

Complete each line of code by filling in the missing parts.

___ i in range(len(items)): if items[i] == target: return i

for i in range(len(items)): if items[i] __ target: return i

for i in range(len(items)): if items[i] == target: return i return __

for i in range(len(items)): if items[i] == target: _____

for i in range(___(items)): if items[i] == target: return i

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A def find(nums, target):

B for i in range(len(nums)):

C if nums[i] = target:

D return i

E return -1

Question 2

A def find(ids, goal):

B for i in range(len(ids)):

C if ids[i] != goal:

D return i

E return -1

Question 3

A def find(pets, name)

B for i in range(len(pets)):

C if pets[i] == name:

D return i

E return -1

Question 4

A def find(pets, name):

B for i in range(pets):

C if pets[i] == name:

D return i

E return -1

Question 5

A def search(nums, target):

B for i in range(len(nums)):

C if nums[i] == target:

D return target

E return -1

Answer Key

Linear search in Python

Section A: Quick Questions

B — for i in range(len(scores)):

B — Checks each item in order until it finds the target or reaches the end

A — return i straight away

A — -1

A — if names[i] == target:

Section B: Match the Pairs

for i in range(len(items)): → Loops through every index of the list so each item can be checked in turn

if items[i] == target: → Compares the current item with the value being searched for

When the target is found, the search stops and gives back its position (index) → return i

If the loop finishes without finding the target, the search returns -1 to show it is not in the list → return -1

if items[i] = target: → Uses = (assignment) instead of == (comparison), which causes a syntax error. It should be ==.

for i in range(len(items)): if items[i] == target: return i return -1 → return -1 is inside the loop, so the search gives up after checking only the first item. It should be after the loop, not inside it.

Section C: Definitions

linear search — An algorithm that uses a loop to check each item in a list in turn. It stops when it finds the target or reaches the end of the list, often returning the index or -1.

Section D: Fill in the Blanks

for i in range(len(items)):
    if items[i] == target:
        return i

for i in range(len(items)):
    if items[i] == target:
        return i

for i in range(len(items)):
    if items[i] == target: return i
return -1

for i in range(len(items)):
    if items[i] == target:
        break

for i in range(len(items)):
    if items[i] == target:
        return i

Section E: Spot the Error

C — A single = assigns a value, so it causes a syntax error inside an if. Use == to compare: if nums[i] == target:

C — With != the function returns the index of the first item that is NOT the goal. Linear search must check for a match using ==.

A — A function definition must end with a colon. It should be def find(pets, name):

B — range() needs a number, not a list. Use len(pets) to get the length: for i in range(len(pets)):

D — Linear search should return the index where the target was found. Returning target just gives back the value we already knew. It should be return i.