Big Idea 3 · Topic 3.11 · Exercise 2
Sorted or Not?
25 minutes - 5 data sets - can you binary search it, and what does it cost?
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.
The cases, from your handoutNot recorded
The same cases as your handout, in the same order.
Scenario 1 · Foundational
A sorted list of 8 exam scores: [55, 61, 68, 72, 79, 85, 90, 96]. You need to find whether 79 is present.
Can binary search be used (is it sorted)? Yes / No + why:
If yes: worst-case binary checks (by halving) vs worst-case linear checks (n):
Enrichment - a subtler ordering or efficiency consideration:
Scenario 2 · Core
An unsorted list of 8 scores as they were entered: [72, 55, 90, 61, 96, 68, 85, 79]. A teammate wants to binary search it for 79 immediately.
Can binary search be used (is it sorted)? Yes / No + why:
If yes: worst-case binary checks (by halving) vs worst-case linear checks (n):
Enrichment - a subtler ordering or efficiency consideration:
Scenario 3 · Core
A sorted list of 63 product IDs (already in ascending order). You need the worst-case number of checks to find any single ID.
Can binary search be used (is it sorted)? Yes / No + why:
If yes: worst-case binary checks (by halving) vs worst-case linear checks (n):
Enrichment - a subtler ordering or efficiency consideration:
Scenario 4 · Challenge
A list of 16 temperatures sorted from HIGHEST to lowest: [98, 95, 91, 88, ...]. A student says binary search is impossible because it is 'backward.'
Can binary search be used (is it sorted)? Yes / No + why:
If yes: worst-case binary checks (by halving) vs worst-case linear checks (n):
Enrichment - a subtler ordering or efficiency consideration:
Scenario 5 · Challenge
A list that is almost sorted, with one value out of place: [10, 20, 30, 85, 50, 60, 70, 40]. A teammate says 'close enough' to binary search for 50.
Can binary search be used (is it sorted)? Yes / No + why:
If yes: worst-case binary checks (by halving) vs worst-case linear checks (n):
Enrichment - a subtler ordering or efficiency consideration:
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.