Algorithms & Data Structures

Module 1 – Algorithms & Data Structures · 1

Page 3 of 3 · About 15 minutes per lesson, including practice.

Binary search needs an invariant

15-minute session: read for 3 minutes, trace for 3, experiment for 7, and complete the check for 2. Spend longer whenever you need.

Binary search relies on sorted data and a shrinking search interval. A faster loop on unsorted data can return a wrong answer. Use a library operation, test insertion at both ends and an existing value, then explain the invariant before implementing your own.

Practice and evidence: Predict the example or draw its state transitions. Change one assumption, test the boundary, and record the actual result. Explain what this small model does not establish about a production system.

from bisect import bisect_left
values=[2,4,6]
print(bisect_left(values,1))
print(bisect_left(values,4))
print(bisect_left(values,8))

Expected result: 0 1 3

Practice and evidence

Keep three notes: your prediction, the actual result, and why they match or differ. The completion check grades understanding; the practice task builds skill.

Example code on Agila Forge ↗