Lesson 8: Algorithms — Searching and Sorting

An algorithm is a precise procedure for solving a problem — a recipe a computer can follow without judgement. The same problem can have many algorithms, and they are not equal: one finds a name in a million entries in 20 steps, another needs a million. This lesson teaches the two fundamental searches, how bubble sort works from the inside, and Big-O notation — the language programmers use to predict how an algorithm's cost grows. These ideas underpin the whole of computer science; the advanced Algorithms course builds directly on them.

Linear search: check everything, in order

The simplest search looks at each item in turn until it finds the target or runs out of list:

def linear_search(data, target):
    """Return the index of target in data, or -1. Counts comparisons."""
    comparisons = 0
    for i, value in enumerate(data):
        comparisons += 1
        if value == target:
            print(f"Found {target} at index {i} after {comparisons} comparisons")
            return i
    print(f"{target} not found after {comparisons} comparisons")
    return -1

numbers = [4, 8, 15, 16, 23, 42]
linear_search(numbers, 23)
linear_search(numbers, 100)

Output:

Found 23 at index 4 after 5 comparisons
100 not found after 6 comparisons

Linear search works on any list, sorted or not, and its cost is proportional to the list's length: worst case, it inspects every item. That cost is written O(n) — "order n" — meaning the work grows in direct proportion to the input size n. Double the data, double the time. For a shopping list that is nothing; for a billion records it is the whole game.

Binary search: halve, halve, halve

If the list is sorted, you can be far cleverer. Compare the target with the middle item. If it is bigger, the target can only be in the right half; if smaller, only in the left half. Discard the impossible half and repeat:

def binary_search(data, target):
    """Search a SORTED list; return the index or -1, printing each probe."""
    lo = 0
    hi = len(data) - 1
    steps = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        steps += 1
        print(f"Step {steps}: check index {mid} (value {data[mid]})")
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

data = [1, 3, 5, 7, 9, 11, 13]
print("Result:", binary_search(data, 11))
print("Result:", binary_search(data, 4))

Output:

Step 1: check index 3 (value 7)
Step 2: check index 5 (value 11)
Result: 5
Step 1: check index 3 (value 7)
Step 2: check index 1 (value 3)
Step 3: check index 2 (value 5)
Result: -1

Trace the search for 11: the middle of the whole list is index 3 (value 7); 11 is bigger, so the left half is discarded and lo moves to 4. The middle of what remains is index 5 (value 11) — found in two probes. The search for 4 probes 7 (too big, discard right), 3 (too small, discard left), 5 (too big, nothing left) and correctly reports -1. Every probe halves the suspect range, so the step count grows with the logarithm of n: binary search is O(log n).

How powerful is halving? This demo counts how many halvings shrink a range to a single candidate:

def binary_steps(n):
    steps = 0
    size = n
    while size > 1:
        size //= 2
        steps += 1
    return steps

for n in [8, 100, 1024, 1_000_000]:
    print(n, "->", binary_steps(n), "halvings")

Output:

8 -> 3 halvings
100 -> 6 halvings
1024 -> 10 halvings
1000000 -> 19 halvings

A million items need 19 halvings — plus the final check, roughly 20 probes against linear search's million. That is the difference between a search that feels instant at any scale and one that collapses as data grows. The price is the precondition: the list must be sorted first, and maintained sorted as data changes.

Big-O: the growth-rate league table

Read the last row carefully. O(n^2) work on a million items is a trillion operations — hours of computing — while O(n log n), the cost of a good sort (about 20 million operations here), is a blink. Big-O ignores constant factors and small inputs to expose the one thing that decides feasibility at scale: how the cost grows. Two more landmarks: O(1) is constant work (a dictionary lookup, roughly, however big the dictionary), and O(2^n) is exponential — fine for n = 20, hopeless for n = 100.

Bubble sort and Python's sorted()

Sorting arranges items in order. Bubble sort repeatedly walks the list swapping adjacent pairs that are out of order; after each pass the largest remaining item has "bubbled" to its final position:

def bubble_sort(data):
    """Return a sorted copy of data, printing the list after each pass."""
    result = data[:]
    n = len(result)
    for pass_no in range(n - 1):
        for i in range(n - 1 - pass_no):
            if result[i] > result[i + 1]:
                result[i], result[i + 1] = result[i + 1], result[i]
        print(f"After pass {pass_no + 1}:", result)
    return result

print(bubble_sort([5, 2, 9, 1]))

Output:

After pass 1: [2, 5, 1, 9]
After pass 2: [2, 1, 5, 9]
After pass 3: [1, 2, 5, 9]
[1, 2, 5, 9]

Three passes for four items, and the inner comparisons shrink each pass (n - 1 - pass_no) because the tail is already sorted. The total work is roughly n^2/2 comparisons — O(n^2) — which is why you will never sort real data this way. Python's built-in sorted() uses Timsort, an O(n log n) hybrid, and accepts a key function for ranking by something other than the items themselves:

names = ["pear", "fig", "banana", "kiwi"]
print(sorted(names))
print(sorted(names, key=len))
print(sorted(["10", "9", "100"]))
print(sorted([10, 9, 100]))

Output:

['banana', 'fig', 'kiwi', 'pear']
['fig', 'pear', 'kiwi', 'banana']
['10', '100', '9']
[9, 10, 100]

Study the last two lines: the strings sort as text — "10" before "100" before "9", because string comparison works character by character and "1" beats "9" — while the numbers sort numerically. Sorting data that arrived as text (from a file, from input()) without converting it first is a real-world bug factory; Lesson 13's CSV work depends on remembering it.

Common mistakes

• Running binary search on an unsorted list. It does not complain; it just lies. binary_search([9, 1, 7, 3], 3) — using the function from this lesson — prints its two probes and returns -1, even though 3 is sitting in the list. The precondition is the contract: sorted in, truth out.
• Forgetting to move lo or hi past mid. Writing lo = mid instead of lo = mid + 1 can leave the range unchanged, and the while loop spins forever. Each iteration must shrink the range.
• data = data.sort(). The list method sort() rearranges in place and returns None — so that line replaces your list with None. Either call data.sort() on its own line, or use data = sorted(data).
• Sorting numbers stored as strings. "10" < "9" as text. Convert with int() when the values arrive (Lessons 2 and 13), not after the sort looks wrong.
• Reaching for a loop when a built-in exists. Hand-rolled sorting in production code is slower and buggier than sorted(). Write bubble sort to *understand* sorting; use Timsort to *do* sorting.

Real-World Challenge

The task. A game stores players and scores as (name, score) pairs. Produce a leaderboard: the top 3 players by score, highest first. Then, given the alphabetically sorted list of player names, use binary search (reuse the function from this lesson — cumulative code is normal in real projects) to check whether a particular player is registered.

Worked solution.

players = [("Ada", 420), ("Ben", 385), ("Cid", 510), ("Dee", 460), ("Eli", 385)]
ranked = sorted(players, key=lambda p: p[1], reverse=True)
print("Top 3:")
for place, (name, score) in enumerate(ranked[:3], 1):
    print(f"{place}. {name} - {score}")

names_sorted = sorted(name for name, _ in players)
print(names_sorted)
print("Is 'Cid' playing?", binary_search(names_sorted, "Cid") != -1)

Output:

Top 3:
1. Cid - 510
2. Dee - 460
3. Ada - 420
['Ada', 'Ben', 'Cid', 'Dee', 'Eli']
Step 1: check index 2 (value Cid)
Is 'Cid' playing? True

How it works. sorted ranks the pairs with key=lambda p: p[1] — compare each pair by its second element, the score — and reverse=True puts the highest first; slicing [:3] takes the podium. The names list is built by a generator expression that unpacks each pair and keeps only the name, then sorted alphabetically — the exact precondition binary search demands. The search probes the middle name once (Cid, index 2) and finds the target immediately, so the check prints True. Note the two different orderings of the same data — by score for glory, by name for lookup — because different questions need different sorts.

Extension. Ben and Eli tie at 385. Make the leaderboard fair and deterministic for ties by sorting on two keys: score descending, then name ascending — sorted(players, key=lambda p: (-p[1], p[0])). Explain to yourself why negating the score reverses only that key, then add a sixth player who ties for third and show the podium is now alphabetical within the tie.

Going further — finding every match

The searches in the main lesson stop at the first hit, because that is what most callers want. Often the honest question is *where does this occur, everywhere?* — duplicate entries in a register, every failing sensor reading, all the positions of a word. The comprehension form generalises the linear search without new machinery:

def find_all(numbers, target):
    return [i for i, n in enumerate(numbers) if n == target]

print(find_all([5, 2, 9, 2, 7, 2], 2))

Output: [1, 3, 5] — three indices, in order, because enumerate walks left to right and the comprehension keeps what matches. Returning a list (possibly empty) rather than a sentinel keeps the contract clean: callers can ask len(...), iterate it, or truth-test it, and "not found" is just the empty case rather than a special value like -1 that someone will eventually use as an index by accident. Performance honesty applies too: this is still a linear scan — finding k matches costs the same full pass as finding one. The algorithmic lesson of the main content stands: choose the structure (sorted data, sets, dictionaries) to match the question you will ask repeatedly, and let each individual search be as simple as it can be.