← Back to course
Code Crew G5 / Week 07 / Tuesday
2/6
Week 07 · Binary search

Tuesday

Halving the catalog
// Cut it in half
⏱ about 15 min

Tuesday: Halving the catalog

Every star now has an ID number. Nova keeps the IDs in a list, sorted from smallest to biggest.

Rocket needs star 27. He starts at the front out of habit. Then he stops himself. "Wait. This list is sorted!"

Raven smiles. "What do you notice about the number in the middle?"

"It is 15," Rocket says. "27 is bigger, so it must be on the right side."

Nova glows. "Great discovery! Here is a hint. Keep track of where the possible part starts and ends."

low, high and mid

We keep two spot numbers. The variable low is the first spot still possible. The variable high is the last one.

The middle spot is mid = (low + high) // 2. The // sign divides and drops any remainder, so 7 // 2 is 3.

print(7 // 2)
print(8 // 2)
print((4 + 7) // 2)
Output:
3
4
5
Spot01234567
ID38121521273036
  1. low is 0 and high is 7. mid is (0 + 7) // 2, which is 3. Spot 3 holds 15.
  2. 27 is bigger than 15, so the target is right of mid. Set low to 4.
  3. mid is (4 + 7) // 2, which is 5. Spot 5 holds 27. Found it in 2 checks!
Search for 30. First mid is spot 3, holding 15. What is the second mid spot?
Spot 5 holds 27, and 30 is bigger. low becomes 6. What is the third mid spot?
How many checks did it take to find 30?
SEARCH FOR 8 IN THE SAME LIST.
  • Read the question.
  • Tap your answer.
The first mid holds 15. Which way do you go?
Now low is 0 and high is 2. What is mid?

Practice lab: find the middle

print(9 // 2)
print(10 // 3)
print((0 + 9) // 2)
print((5 + 9) // 2)
What does print(9 // 2) show?
What does print(10 // 3) show?
What does print((0 + 9) // 2) show?
What does print((5 + 9) // 2) show?
Spot0123456
ID25914202331
SEARCH THIS LIST BY HAND.
  • Read the question.
  • Tap your answer.
Search for 5. low is 0 and high is 6. mid is 3, holding 14. What is high next?
Now low is 0 and high is 2. What is mid?
Search for 23. How many checks does it take?
StatementTrue or false?
The first mid for this list is spot 3.?
8 // 2 is 4.?
7 // 2 is 3.5.?
low and high mark the part of the list still possible.?
WHY THIS EXERCISElow, high and mid are spot numbers, so they must be whole.
low is 2 and high is 6. What is mid?
WHY THIS EXERCISE8 divided by 2 is 4, with nothing left over.

Nice halving! You searched a sorted list the way a computer does. Tomorrow we read the binary search code.

← Monday