← Back to course
Intro to CS 9-10 / Week 05 / Thursday
4/6
Week 05 · Lists

Thursday

Searching and simplifying
// Keeping track of many values at once
⏱ about 20 min

Thursday: Searching and Simplifying

A message comes in from the greenhouse team. "Did the water ever drop to 48 yesterday?"

Comet points at the cards. "Easy. I can see it right there."

Wren turns all six cards face down. "Beacon cannot see the whole row at once. It checks one card at a time."

Comet flips the first card. 62. Then the second. 58. Then the third. 54.

She flips the fourth and laughs. "48! Found it in four checks."

Nova hovers beside Comet. "Great discovery," she says. "Now, what if the reading was never there?"

Comet thinks for a moment. "Then I would have to check every card before I could say no."

Linear search

A linear search, also called a sequential search, checks each element of a list in order.

It stops when it finds the value it wants, or when every element has been checked.

index ← 1
found ← false
REPEAT UNTIL (found OR index > 6)
{
  IF (readings[index] = 48)
  {
    found ← true
  }
  ELSE
  {
    index ← index + 1
  }
}

This search uses last week's REPEAT UNTIL loop. It stops when found is true, or when index runs past the end.

The condition index is greater than 6 keeps the search from asking for an index out of range.

TRACE THE SEARCH
  • Read the question.
  • Tap your answer.
How many elements does the search check before it finds 48?
What is index when the loop stops?
If the target were 50, which is not in the list, how many elements would be checked?
If the target were 62, how many elements would be checked?

Replace six variables with one list

Developers look for repeated code that differs only a little. Then they swap in one segment that uses a list.

Here is Comet's old code, and the list version that replaces it.

Old code                       List version
DISPLAY(reading1)              FOR EACH reading IN readings
DISPLAY(reading2)              {
DISPLAY(reading3)                DISPLAY(reading)
DISPLAY(reading4)              }
DISPLAY(reading5)
DISPLAY(reading6)

A list lets many related items be treated as one value. Giving a collection one name, without its details, is a data abstraction.

Data abstractions manage complexity. The program talks about readings, not about six separate boxes.

StatementTrue or false?
A linear search checks elements in order, one at a time.?
A linear search can say a value is missing after checking only the first element.?
The list version works for 24 readings without adding new lines.?
A data abstraction gives a collection of data one name.?
WHY THIS EXERCISESearching and simplifying are the two big reasons lists make programs better.
STEPS OF A LINEAR SEARCH
  • ?Start at the first element.
  • ?If it matches, stop: the value is found.
  • ?If not, move to the next element and compare again.
  • ?Compare the element with the value you want.
  • ?If you pass the last element, stop: the value is not in the list.
WHY THIS EXERCISEA linear search is a sequence, a selection and an iteration working together.
Another name for a linear search is a ____ search. Type the missing word.
WHY THIS EXERCISEBoth names describe checking each element in order.
Try it
Ask a partner to write eight numbers on cards and lay them face down in a row.
Search for one number by flipping cards in order. Count your checks.
LISTS OR SEPARATE VARIABLES?
  • Read the question.
  • Tap your answer.
Beacon must store the temperature at each of 24 hours.
Beacon must store just the greenhouse name.
Beacon must store the names of all the plants on a shelf.
On paper, sketch a flow chart of the linear search. Use a diamond for the question: is this the value I want?

Sharp thinking. Tomorrow is Impact Friday: what happens when many people add to one list?

← Wednesday