The Life Starter
0 of 6 complete0%
Course Library · Lesson 3 of 6
Digital · Guided lesson

Keep a sorted search invariant

About 14 minutes · 4 reading + 10 practice and checks
Time includes reading, practice, and questions. Extra videos or further study are optional.
See this course’s project requirements

A tested Python catalog search with linear and binary methods, comparison counts, sortedness checks and a justified method choice.

Keep your working files in your own notebook or software. Save a private description, checklist, and work link in My Proof.

What to include

  • A three-case lookup contract with results 5,-1,-1.
  • A linear-search trace with six and seven comparisons.
  • A sortedness rule and two-step interval trace.
  • A terminating binary-search implementation and boundary trace.
  • A cost comparison distinguishing lookup from total work.
  • A checked algorithm-comparison packet with honest measurement limits.

Review and revise

Use these criteria to check your work and choose what to improve.

  • The implementation or declared simulation follows the supplied contract and retains inspectable original inputs.
  • Normal, boundary and rejected cases are recorded with expected versus observed results.
  • The changed case has a correct explanation and does not rely on hidden state.
  • The project includes source, outputs, instructions and honest tool, privacy and verification limits.
Open the full course project
Want more background?
Before you begin

The idea in everyday life

Sorted IDs are [12,18,25,31,44,52,67]. For 52, low 0 high 6 gives middle 3 and value 31.

The idea

Binary search may discard half the candidates only when ordering proves that they cannot contain the target. Keep the target, if present, within inclusive low/high bounds.

Follow along

Keep a sorted search invariant — original worked practice

Binary search may discard half the candidates only when ordering proves that they cannot contain the target. Keep the target, if present, within inclusive low/high bounds.

Sorted IDs are [12,18,25,31,44,52,67]. For 52, low 0 high 6 gives middle 3 and value 31.

  1. 1. Step 1

    Compare 52 with middle 31.

    You should see: Because 52>31, indexes 0–3 can be discarded.

    This keeps the rule and its observable result together.

  2. 2. Step 2

    Update low to 4 and retain high 6.

    You should see: The remaining interval contains 44,52,67.

    This keeps the rule and its observable result together.

  3. 3. Step 3

    Compare middle index 5 with 52.

    You should see: The second midpoint probe matches.

    This keeps the rule and its observable result together.

  4. 4. Step 4

    Write the reason unsorted [52,12,31] is rejected.

    You should see: A sortedness rule and two-step interval trace.

    This keeps the rule and its observable result together.

Now change one thing

For target 18, the first middle remains 31. Enter the new high index.

Your work

What to finish

A sortedness rule and two-step interval trace.

Common mistake

Watch for this

Applying binary lookup to unsorted inputs; the discarded half can contain the sought ID.

How can I tell I understand it?

Explain and demonstrate the required distinction: Binary search may discard half the candidates only when ordering proves that they cannot contain the target. Keep the target, if present, within inclusive low/high bounds. Show a changed input and the expected result without weakening this contract.

Try 3 questions

Quick knowledge check

Answer all 3 questions. Get at least 2 right and the lesson completes automatically.

Not yet passed

You’ll get an explanation for each answer. Signed in? Your results save to your account.

1After 52 is compared with 31 at index 3, what is new low?
2Which condition justifies discarding the left half?
3What should the supplied binary function do with [3,1]?
0 of 3 answeredApply the lesson to a short question, then review the explanation.
3
Finish this lesson

Pass the check. We’ll save the progress.

Answer all 3 questions above and get at least 2 right. You can review the explanations and try again.

Go to the knowledge check
Tools, templates, and lesson sources

Tools and templates

Tools open in a new tab so you can keep your place here.

Sources and further reading

Explore the references behind this lesson.

docs.python.org — bisect.html
Source & access notes · checked 2026-10-01

Relevant documented module/API behavior inspected during expansion authoring; actual execution evidence is recorded separately. No grant eligibility is established.

Access: Official page retrieved with the web reader on 2026-10-01. Documentation reading does not certify execution in every native tool or browser.

Reuse: Original local practice files, fictional data, worked examples and questions. Concepts paraphrased and linked; source exercises are not copied.

docs.python.org — data structures.html
Source & access notes · checked 2026-10-01

Relevant documented module/API behavior inspected during expansion authoring; actual execution evidence is recorded separately. No grant eligibility is established.

Access: Official page retrieved with the web reader on 2026-10-01. Documentation reading does not certify execution in every native tool or browser.

Reuse: Original local practice files, fictional data, worked examples and questions. Concepts paraphrased and linked; source exercises are not copied.

Report a problem with this lesson

Tell us what went wrong. Please leave out personal information and private project contents.

No sign-in needed.