Big Idea 3 · Topic 3.11 · Exercise 1
Trace the Shelf
25 minutes
Back to the Topic 3.11 lessonAll CSP topics
How this page works
The writing boxes below are yours. What you type stays in this browser, is saved here as you go, and is never sent to us or to your teacher. Hand the written work in the way your teacher asked for it.
The graded check at the bottom is the part that records to your teacher's gradebook.
Part B, from your handoutNot recorded
Your handout says these are the same items available here. Part A stays on paper.
Q1 · 3 points on the handout
Suppose the shelf had NOT been sorted first. Explain, using iteration 1 as an example, why binary search could then throw away the half that actually contains book 47.
Q2 · 3 points on the handout
Linear search would also find book 47 on this shelf. State the worst-case number of checks for each search on the 15-book shelf, and explain what makes binary search often more efficient here.
Q3 · 2 points on the handout
ENRICHMENT: The shelf grows from 15 books to 31 books (still sorted). Predict the new worst-case number of binary search checks by halving, and explain why roughly doubling the shelf added so few checks.
Q4 · 0 points on the handout
Next step: you traced these searches by hand. Now head to the Topic 3.11 page and type and run the harder versions, where the computer checks your output for you.
No graded check on this page yetNot recorded
About the line in your handout
Your handout says this exercise is available online and auto-graded. The exercise IS here, and it is the same work in the same order, but the auto-graded half is not written for this topic yet. Nothing on this page is scored or sent to your teacher.
Hand this in the way your teacher asked for it. Topic 1.1 has its graded check today, and the rest follow.