Week 13 — Lecture Outline · Algorithms: Searching & Sorting + Intro to Complexity

Course: Introduction to Computer Science — CS1 / Programming Fundamentals in Python (CSCI 1101) · Silver Oak University (fictional sample) · Prof. Okafor
Objective covered: Objective 8 — Apply foundational algorithms (linear & binary search, a simple sort) and reason informally about Big-O.
SLOs touched: A (implement & run algorithms) · B (trace behavior; count steps; find a defect)
Meeting pattern: 2 studio sessions × 75 min = 150 min. (Thursday is the Thanksgiving holiday; compress to one session or carry Segments 5–8 to the next meeting.)

Every comparison count and output below was produced by running instrumented code in Python — not estimated. Run them live.

---

Week at a Glance

Big question	"Two programs get the same answer — why is one a thousand times faster?"
By end of week, students can…	(1) implement linear and binary search; (2) explain why binary needs a sorted list; (3) count comparisons and compare the two; (4) trace a selection sort; (5) name the Big-O (O(n), O(log n), O(n²), O(1)) intuitively.
Key vocabulary	algorithm, linear search, binary search, sorted, comparison, selection sort, swap, efficiency, complexity, Big-O, O(1), O(log n), O(n), O(n²)
Materials	slides (Deck 13), readings, the online editor + Python Tutor, one approved chatbot
Timing note	8 segments, ~150 min. Students type and run every instrumented example.

---

Segment 1 — Hook & the Promise (8 min)

Hook. "I'm thinking of a number 1–100. Guess it; I'll say higher or lower." The room lands it in ~7 guesses, not 100 — because they halve the range each time. "That's binary search, and today you'll see why halving beats checking-one-at-a-time by a landslide — and how we measure that difference."

Promise: "By Friday you'll implement two searches, count their steps on the same list, and watch one win 13-to-4."

Memory hook: "Binary search halves the list — but only if it's sorted."

---

Segment 2 — Linear Search + Counting Comparisons (22 min) · code-along

Plain language. Linear search checks each element in order until it finds the target (or runs out). Its cost grows with the list length.

Code-along (instrument it — count comparisons):

def linear_search(lst, target):
    comparisons = 0
    for i in range(len(lst)):
        comparisons += 1
        if lst[i] == target:
            return i, comparisons
    return -1, comparisons

data = [4, 8, 15, 16, 23, 42]
print(linear_search(data, 16))   # run-verified -> (3, 4)
print(linear_search(data, 42))   # run-verified -> (5, 6)
print(linear_search(data, 7))    # run-verified -> (-1, 6)  not found

"Finding 16 took 4 comparisons; finding 42 (the last item) took 6; a missing value takes 6 — it checks everything. For a list of n items, worst case is n comparisons. That's O(n)."

---

Segment 3 — Binary Search (the worked trace) (24 min)

Plain language. Binary search works only on a sorted list. Check the middle: if it's the target, done; if the target is bigger, throw away the left half; if smaller, throw away the right half. Repeat on what's left.

Code-along (instrument it):

def binary_search(lst, target):
    lo, hi = 0, len(lst) - 1
    comparisons = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        comparisons += 1
        if lst[mid] == target:
            return mid, comparisons
        elif lst[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, comparisons

data = [4, 8, 15, 16, 23, 42]   # sorted
print(binary_search(data, 16))  # run-verified -> (3, 3)
print(binary_search(data, 4))   # run-verified -> (0, 2)
print(binary_search(data, 7))   # run-verified -> (-1, 3)  not found

The headline comparison (run live on a 16-item sorted list [1..16]):
- linear_search finding 13 → run-verified 13 comparisons.
- binary_search finding 13 → run-verified 4 comparisons.
"Same answer (index 12), but 13 steps vs. 4. Double the list to 32 and linear needs ~32 while binary needs ~5. That halving is O(log n) — the reason binary search matters."

---

Segment 4 — Selection Sort (the worked trace) (20 min) · Session 1 closes

Plain language. To use binary search you need a sorted list. Selection sort: repeatedly find the smallest remaining item and put it in place.

def selection_sort(a):
    a = a[:]                       # work on a copy
    for i in range(len(a)):
        m = i
        for j in range(i + 1, len(a)):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]    # swap smallest into position i
    return a

print(selection_sort([5, 2, 9, 1, 7]))  # run-verified -> [1, 2, 5, 7, 9]
print(selection_sort([3, 1, 2]))         # run-verified -> [1, 2, 3]

"Notice the loop inside a loop — for each of n positions we scan the rest. That's about n×n work: O(n²), which is why big sorts use cleverer algorithms (a CS2 topic)."

---

Segment 5 — Big-O, Intuitively (20 min) · Session 2 opens

Plain language — Big-O describes how the work grows as the input grows, not the exact step count.

Big-O	Name	Example	Feel
O(1)	constant	lst[5] — direct index	instant, size doesn't matter
O(log n)	logarithmic	binary search	halving — very fast
O(n)	linear	linear search	grows with the list
O(n²)	quadratic	selection sort (loop in a loop)	slows down fast

"Big-O ignores constants and small terms — it answers 'what happens when the list gets 1,000× bigger?' O(1) shrugs; O(log n) barely notices; O(n) keeps up; O(n²) falls over."

---

Segment 6 — Spot & Fix the Bug: Binary Search on Unsorted (18 min)

The buggy program. Run binary search on an unsorted list:

data = [8, 4, 23, 16, 42, 15]   # NOT sorted
print(binary_search(data, 4))   # run-verified -> (-1, 2)   says NOT FOUND!

"But 4 is in the list, at index 1! Binary search reported 'not found.' It wasn't a code typo — the precondition was violated: binary search assumes sorted order to decide which half to throw away."

The fix — sort first (or use linear search):

data = sorted([8, 4, 23, 16, 42, 15])  # -> [4, 8, 15, 16, 23, 42]
print(binary_search(data, 4))           # run-verified -> (0, 2)   correct

Land the idea: some bugs aren't typos — they're broken assumptions. Always ask what an algorithm requires.

---

Segment 7 — Misconceptions Round-Up + Interaction (20 min)

• ❌ "Binary search works on any list." ✅ Only a sorted one — otherwise it gives wrong answers (Segment 6).
• ❌ "Binary search is always faster." ✅ For a tiny list, or an unsorted one you'd have to sort first, linear can win; binary's advantage grows with size.
• ❌ "Big-O is the exact number of steps." ✅ It's how the work grows — constants and small terms drop.
• ❌ "You can't measure speed without a stopwatch." ✅ Count comparisons — it's deterministic and run-verifiable.

Interaction — predict-then-run: give the room a sorted 8-item list; have them predict binary-search comparisons for a few targets, then run the instrumented version and check.

---

Segment 8 — Technology Workflow + AI-Critique, Callback & Hand-off (18 min) · Session 2 closes

Technology workflow: (1) write the search/sort; (2) add a comparisons counter and print it; (3) run it on lists of different sizes and watch the counts; (4) visualize the loop in Python Tutor.

AI-critique moment:

Ask a chatbot: "How many comparisons does binary search take to find 13 in the sorted list 1 to 16? And does binary search work on an unsorted list?" Then check by running an instrumented version: chatbots often miscount (say 3 or 5 instead of the run-verified 4) and frequently claim binary search works on unsorted data (it doesn't — Segment 6). The tool drafts; you run it and judge.

Callback + tease:
- Callback: "Same answer, very different cost — and you measured it by counting."
- Tease next week: "We've used loops to repeat. Next week a function calls itself — recursion — and we watch the call stack grow and shrink in Python Tutor."

Hand-off: Lecture Tutorial 13; Quiz 13; Discussion 13 ("Who Decides the Ranking?"); Assignment 13 ("Search, Sort, Count"); Coding Lab 13 — "Count the Steps."

---

Instructor FAQ — Common Stumbles

Student says / does	Quick cure
Runs binary search on an unsorted list.	It needs sorted input or it gives wrong answers — sort first.
Thinks binary search is always fastest.	Only as the list grows; tiny/unsorted lists can favor linear.
Off-by-one in hi = len(lst) .	Use hi = len(lst) - 1 (last valid index); the loop is while lo <= hi.
Treats Big-O as an exact count.	It's the growth rate — drop constants and small terms.
Can't say how fast a search is.	Add a comparisons counter and run it.

---

Scope flag

This outline keeps Big-O light and intuitive — no formal definitions, proofs, or amortized analysis (CS2). One simple sort (selection) is enough to feel O(n²); merge/quicksort and other data structures are deferred. Named algorithms and Big-O notation are referenced factually; the instructor and institution remain fictional. Every comparison count was produced by running the code.