brightoolhub. Français

Computer science · 04 / 06

Loops and search: trace the algorithm

High school · intermediate · Worked example and 4 exercises with solutions, at your pace.

Need a foundation?Binary: position determines weightAlgorithms: inputs, steps, output
UnderstandSee an exampleGuided exercise3 progressive challenges

The principle, simply

Loops repeat operations with state and continuation conditions. Linear search inspects entries until success or end. Binary search halves a search interval but usually requires sorted data. An invariant persists across steps; a decreasing measure can justify termination.

THE PICTURE TO REMEMBERLoops and search: trace the algorithm
  1. 01Inputs
  2. 02State and invariant
  3. 03Progress
  4. 04Exit and boundaries

WORKED EXAMPLE

From principle to reasoning

Searching [2,5,9,12] for 9 checks 2,5,9. Summation starts at zero and adds each element once. Trace index, value, accumulator and condition.

Solve a problem in this subject

  1. Specify the contract

    Define inputs, types, outputs and forbidden cases. State whether a search algorithm requires sorted data.

  2. Trace a small example

    Tabulate variables, tested conditions and actions using a small hand-checkable example.

  3. Test boundaries

    Consider empty inputs, one item, duplicates, missing values and numeric limits where relevant. Define the output or explain rejection.

  4. Justify

    Explain termination and correctness. Distinguish operation counts, measured time and memory use.

YOUR TURN

01 · Try before checking

Why might a while loop with a permanently true condition never finish?

One hint

What update brings the condition towards false?

Reveal and understand the solution

Without progress or explicit exit, no state reaches termination. Justify progress, not merely the condition.

Compare method, conditions and answer; identify the exact part to revisit.

IMPROVE THROUGH PRACTICE

Three additional challenges with solutions

Start with the first challenge. Write your method before opening a hint; use the solution to find the first step that needs work.

Reflect after practising
02 · Recognise and understandLink to this exercise

How many iterations does Python range(2,6) produce?

A hint to get started

The end bound is excluded.

Step-by-step solution
  1. The values are 2,3,4,5.
  2. There are four iterations.
  3. 6 is excluded.

Which step did you miss? Retry without help, then explain why the method works.

03 · Apply the methodLink to this exercise

A linear search scans [3,8,2,9] for 2 and stops at success. How many comparisons?

A hint to get started

Start with the first element.

Step-by-step solution
  1. Compare with 3, then 8, then 2.
  2. The third comparison succeeds.
  3. It stops without testing 9.

Which step did you miss? Retry without help, then explain why the method works.

04 · Go furtherLink to this exercise

Why does binary search require a sorted list?

A hint to get started

Discarding half requires reliable ordering.

Step-by-step solution
  1. The middle comparison identifies a side only when order is known.
  2. Without sorting, the discarded half might contain the target.
  3. In sorted data, each step roughly halves the remaining region.

Which step did you miss? Retry without help, then explain why the method works.

The trap to avoid

Binary search needs sorted data; handle boundary cases.

Without notes, can you…

  • Explain the principle in your own words?
  • Rebuild the diagram and its connections?
  • Solve the exercise and justify the method?

Choosing a state saves it in this browser. This is your assessment, not a grade.

Next chapter My notebook