← Back to course
Intro to CS 9-10 / Week 07 / Monday
1/6
Week 07 · Search, Speed and Limits

Monday

Did the water ever read 74?
// Binary search, counting steps, heuristics and problems no algorithm can solve
⏱ about 20 min

Monday: Did the Water Ever Read 74?

A message arrives from mission control. "Did the greenhouse water level ever read exactly 74 this month?"

Comet opens Beacon's log. "Hundreds of readings," she says. "I will just check them one by one."

Wren leans in. "What do you notice about this list?"

Comet squints. "It is sorted. Smallest reading at the top, largest at the bottom."

Nova hovers over the log and lights up the reading in the very middle. "Would you like a hint?" she asks. "Start here."

Comet thinks for a moment, then grins. "If the middle reading is too small, the answer must be in the bottom half."

Wren turns to you. "You are Beacon's developer. Can you turn that idea into exact steps?"

Problems and instances

This week asks a big question: why are some problems fast, some slow, and some impossible for any algorithm?

First, two words. A problem is a general description of a task that can, or cannot, be solved by an algorithm.

An instance of a problem has specific input. Sorting is a problem. Sorting the list 2, 3, 1, 7 is one instance of it.

A decision problem is a problem with a yes or no answer. Mission control just asked one.

PROBLEM, INSTANCE OR DECISION PROBLEM?
  • Read the question.
  • Tap your answer.
Searching a list for a value. Is that a problem or an instance?
Searching the list 12, 18, 23 for the value 18. Is that a problem or an instance?
Did the water level ever read exactly 74? What kind of problem is that?

Linear search, again

You met linear search in week 5. It checks each element of a list in order until it finds the value or has checked them all.

Linear search works on any list, sorted or not. But it can be slow.

If the value is the last element, or is not in the list at all, linear search checks every element.

COUNT THE LINEAR SEARCH CHECKS
  • Read the question.
  • Tap your answer.
A list has 15 readings. The value you want is in position 12. How many checks does linear search make?
A list has 15 readings, and the value you want is not in it. How many checks?
A list has 32 readings. What is the most checks linear search could ever need?

A faster idea needs sorted data

Binary search starts at the middle of a sorted data set and eliminates half of the data.

It repeats this until it finds the value or until every element has been eliminated.

Data must be in sorted order to use binary search. On sorted data, binary search is often more efficient than linear search.

StatementTrue or false?
Binary search starts at the middle of the data.?
Binary search works on a jumbled, unsorted list.?
Each binary search check eliminates about half of the data that is left.?
Linear search only works on sorted lists.?
WHY THIS EXERCISEKnowing what each search needs tells you which one Beacon can use.
PUT THE BINARY SEARCH STEPS IN ORDER
  • ?Repeat with the half that is left, until you find the target or nothing is left.
  • ?Otherwise, eliminate the half that cannot hold the target.
  • ?Look at the middle element of the data still in play.
  • ?Make sure the data is sorted from smallest to largest.
  • ?If the middle element is the target, stop: you found it.
WHY THIS EXERCISEAn algorithm is a finite set of exact steps. These five steps are binary search in plain words.
Which element does binary search check first? Type one word.
WHY THIS EXERCISEStarting in the middle is what lets one check eliminate half the data.
Try it
Find a printed dictionary or the index at the back of a book.
Look up a word. Notice how you open near the middle and skip whole chunks, instead of reading every page.
For a grown-up
This week, your student compares two ways to search a sorted list, using paper cards and pencil.
Everything is unplugged. No lesson asks your student to open an app, a website or an AI tool.
On paper, draw a row of 15 boxes for a sorted list. Shade the middle box, then cross out the half you would skip if the target were bigger.

Good start, developer. Tomorrow you will trace binary search one check at a time.