Lab: search
Time linear vs binary search on growing inputs, implement count_target with binary search, and flatten a nested list recursively as a bonus.
- Compare linear and binary search timing on progressively larger inputs
- Implement count_target using binary search variants to stay O(log n)
- Implement a recursive flatten as a bonus challenge
This is an optional lab. Three checkpoints: the first is observational (run and read the output), the second is a coding exercise, and the third is a bonus that introduces a genuinely recursive problem.
Checkpoint 1 — feel the O(log n) advantage
Before writing any exercise code, run this timing comparison. The data is a sorted list with no duplicates, so binary search always works correctly.
What to look for. As n grows by 10×, linear search time grows by roughly
10×. Binary search time grows barely at all — the number of comparisons
increases by only about 3 (log₂(10) ≈ 3.3). At n=10 000 that difference is
already visible in microseconds; at n=1 000 000 it would be unmissable.
Checkpoint 2 — count target occurrences with binary search
A sorted list may contain duplicates. count_target(lst, target) should return
how many times target appears, in O(log n) time — not O(n).
Think first. Binary search finds an occurrence, but not necessarily the
first or last. If you can find the leftmost and rightmost index of target,
subtracting them gives the count. What invariant change finds the leftmost index
instead of stopping at any match?
Write count_target(lst, target) returning how many times target appears in the sorted list lst. Use binary search variants — do not use a linear scan.
count_target([1, 2, 2, 2, 3, 4], 2) → 3count_target([1, 2, 4, 5], 3) → 0The key insight: instead of stopping when you find a match, you keep narrowing
in the same direction. find_left keeps going right half → left half when it
hits a match; find_right does the opposite. Two binary searches — O(log n)
total.
Checkpoint 3 (bonus) — recursive flatten
This problem has a recursive structure that makes recursion natural. A nested
list like [1, [2, [3, 4]], 5] should flatten to [1, 2, 3, 4, 5]. The list
may be arbitrarily deeply nested.
Think first. A flat list is a base case — just return its elements. A nested list is a recursive case — flatten each element and concatenate. What type check tells you which case you are in?
Write flatten(nested) that takes an arbitrarily nested list of integers and returns a flat list of integers in the same left-to-right order.
flatten([1, [2, [3, 4]], 5]) → [1, 2, 3, 4, 5]This is recursion in its natural habitat: the problem is self-similar (a nested list contains items that may themselves be nested lists), and each recursive call works on a strictly smaller structure. The "call yourself on sublists" pattern appears constantly in tree traversal, file-system walks, and JSON parsing.
Done?
Three checkpoints — one observational, one algorithmic, one recursive. You now have a hands-on feel for the difference O(log n) makes, a concrete binary-search variant, and a recursive algorithm on a genuinely nested structure. That wraps up the CS Fundamentals beginner track.
Search in Python
Implement linear search and iterative binary search, then watch binary search fail on unsorted input to understand why sorted data is a hard requirement.
Stacks
Understand the LIFO principle that makes stacks useful for call tracking, undo history, expression evaluation, and bracket matching.