← Back to course
Code Crew G5 / Week 06 / Monday
1/6
Week 06 · Search one by one

Monday

Check every star
// Linear search and counting checks
⏱ about 15 min

Monday: Check every star

Mission Control sends a message: please confirm that the star Halo is in your catalog.

Rocket scrolls the list so fast that the names blur. "I did not see it. Maybe it is not there?"

Raven slows the list down. "What do you notice if we read one name at a time, from the top?"

They read: Ember, Frost, Glow, Halo. "There it is!" Rocket says. "Spot 3."

Nova flickers. "Here is a hint. Write down the steps you just did. That is an algorithm."

Linear search

Linear search checks each item in order. If an item matches the target, it returns that spot number.

If it checks every item and finds no match, it returns -1. That number means not found, because no spot is -1 here.

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

stars = ["Ember", "Frost", "Glow", "Halo", "Iris"]
print(find(stars, "Glow"))
print(find(stars, "Zephyr"))
Output:
2
-1
  • range(len(items)) gives every spot number: 0, 1, 2, 3, 4.
  • return i stops the search the moment it finds a match.
  • return -1 only runs after the loop has checked every item.
What does print(find(stars, "Iris")) show?
WHY THIS EXERCISEfind returns the spot number where the target was found.
USE FIND WITH THE SAME STARS LIST.
  • Read the question.
  • Tap your answer.
What does find(stars, "Ember") return?
What does find(stars, "Juno") return?
What does find(stars, "halo") return?
Statement about findTrue or false?
find checks the items starting from spot 0.?
find keeps checking after it finds the target.?
return -1 runs when the target is missing.?
WHY THIS EXERCISEreturn ends the function at once, so the search stops at the first match.

Practice lab: search the moons

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

moons = ["Ash", "Bay", "Cove", "Bay"]
print(find(moons, "Bay"))
print(find(moons, "Cove"))
print(find(moons, "Dune"))
What does the first print line show?
What does the second print line show?
What does the third print line show?
What does find(moons, "Ash") return?
MOON CHECK
  • Read the question.
  • Tap your answer.
Bay is in spot 1 and spot 3. Why does find return 1?
What numbers does range(len(moons)) make?
What does find(moons, "bay") return?
StatementTrue or false?
find(moons, "Cove") checks three items.?
find returns the name it found.?
return -1 runs only after the loop ends.?
A list can hold the same name twice.?
WHY THIS EXERCISEKnowing what a function returns helps you use its answer.
How many spot numbers does range(len(moons)) make?
WHY THIS EXERCISEThere is one spot number for each item in the list.

Great searching! Tomorrow we count how many checks a search takes.