01 | WHAT QUESTION ARE YOU ANSWERING?

A scoreboard might need to answer two questions: where is Maya’s entry, and what order should the results appear in? Searching finds a match; sorting arranges a collection according to an ordering rule. Sorting does not itself tell you that the target exists.

Agree a search contract first. The examples here return a zero-based index for a found integer and None when absent. None avoids confusing absence with index zero. Do not test if index, because a successful result of zero is falsey. Test index is not None.

A record’s displayed rank and its list index are different concepts. Moving records during a sort changes positions, so a previously stored index might no longer refer to the same record.

02 | LINEAR SEARCH VISITS IN ORDER

Linear search checks items from the beginning until it finds the target or reaches the end. It works on unsorted data because it does not assume where values belong. The first returned match is the first matching position.

The return inside the loop stops this call when equality holds. The return None belongs after the loop: returning it after the first mismatch would reject targets later in the list.

An empty list performs no iterations and returns None. Repeated values are allowed; this contract returns only the first match, not every matching index.

def linear_search(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return None

print(linear_search([8, 5, 12, 5], 5))
print(linear_search([8, 5, 12], 7))

1
None

03 | BINARY SEARCH REQUIRES ORDERED DATA

For an ascending list, comparing a middle value lets you discard an entire half. If target is smaller, it cannot be in the larger-value half. This reasoning depends on the sorting rule; applying it to unsorted data can miss a target that is present.

low and high are the inclusive endpoints of the active interval. mid = (low + high) // 2 chooses an integer position. On a mismatch, change low to mid + 1 or high to mid - 1 to exclude the position already checked and make progress.

The loop runs while low <= high. If the interval becomes empty, return None. With duplicates, this implementation returns a matching index, not necessarily the first one. State that difference from the linear-search contract.

def binary_search(values, target):
    """Find any target index in an ascending list, or return None."""
    low = 0
    high = len(values) - 1
    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        if target < values[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return None

print(binary_search([2, 5, 8, 12, 16], 12))
print(binary_search([], 12))

3
None

04 | DO NOT LOSE THE MEANING OF AN INDEX

Sorting before binary search has a cost and can change positions. If original = [12, 2, 8] and ordered = sorted(original), finding 12 in ordered gives index two. In original it was index zero. An index belongs to the collection actually searched.

For one small search, linear search can be simpler than sorting first. For many searches on an already ordered dataset, binary search can save repeated comparisons. The next lesson compares growth rather than claiming one method is always better.

Python membership with in is convenient when you only need a yes/no answer. A custom search is helpful for learning the process or returning additional information.

05 | SORTED MAKES A NEW LIST

sorted(values) returns a new list in ascending order and leaves the original list unchanged. values.sort() changes the list in place and returns None. Choose deliberately based on whether the caller needs the original order.

reverse=True requests descending order. Values must support the required comparisons. A list mixing unrelated types such as integers and strings generally cannot be sorted by default in Python 3.

Sorting the order of references does not deeply copy nested record objects. A new sorted list can still contain the same dictionaries as the original collection.

scores = [8, 5, 12]
ordered = sorted(scores)
print("Original:", scores)
print("New list:", ordered)
result = scores.sort(reverse=True)
print("Changed:", scores)
print("sort return:", result)

Original: [8, 5, 12]
New list: [5, 8, 12]
Changed: [12, 8, 5]
sort return: None

06 | SORT RECORDS WITH A KEY FUNCTION

A player dictionary cannot be ordered as if it were an integer. A key function extracts the value Python should use for comparison. Pass the function itself as key=score_key, without calling it there. Python calls it with each record to obtain a sorting key.

Python sorting is stable: records with equal keys retain their input order. With key=score_key and reverse=True, equal-score players still retain their input order. This differs from the previous project’s reverse tuple sort, where names were a secondary key.

A key can return a tuple for an explicit tie policy. (-player["score"], player["name"]) gives highest score first and ascending name when sorted in default ascending order. Keep one documented policy rather than switching between them unexpectedly.

def score_key(player):
    return player["score"]

players = [{"name": "Maya", "score": 8},
           {"name": "Kai", "score": 12},
           {"name": "Noor", "score": 8}]
ranked = sorted(players, key=score_key, reverse=True)
for player in ranked:
    print(player["name"], player["score"])

Kai 12
Maya 8
Noor 8

07 | SEE WHY A SIMPLE SORT REPEATS WORK

Bubble sort is useful for understanding comparisons and swaps. It compares neighbouring items and exchanges them when out of order. One left-to-right pass moves a largest remaining value to the end of the active area. Multiple passes may be needed.

The implementation below sorts a shallow copy so it preserves the input order. end shrinks after each pass because the rightmost value is already in place. swapped allows an early exit when a pass makes no changes.

Use Python’s built-in sorting for ordinary application code. This educational implementation is not an improvement on it. Its purpose is to expose the operations you will compare in the efficiency lesson.

def bubble_sorted(values):
    result = values.copy()
    for end in range(len(result) - 1, 0, -1):
        swapped = False
        for index in range(end):
            if result[index] > result[index + 1]:
                result[index], result[index + 1] = result[index + 1], result[index]
                swapped = True
        if not swapped:
            break
    return result

print(bubble_sorted([8, 3, 5, 1]))

[1, 3, 5, 8]

08 | STEP THROUGH THE SEARCH

Choose a target and compare linear search with binary search on the same ascending integer list. Each step records the inspected index and the decision. For binary search, the interval is shown before it changes. These demonstrations count inspected positions, not all machine instructions.

Data: [2, 5, 8, 12, 16, 20, 24]

09 | USE TESTS THAT EXPOSE ASSUMPTIONS

For linear search, test the first item, last item, absent target, empty list and repeated values. For binary search, also verify the ascending-order assumption and record that duplicate matches need not be the first.

For sorting, test empty, one-item, already ordered, reverse ordered and repeated-value lists. For record sorting, check the tie policy with at least two equal keys.

Compare results against built-in behaviour where the contracts match. Do not assert that every binary-search result equals the first linear-search result when duplicates exist. Both can satisfy their different contracts.

10 | CHOOSE THE TOOL FOR THE JOB

Use membership when you only need presence, linear search when order is unavailable or simplicity matters, and binary search when its ordering assumption is guaranteed and repeated queries justify it. For arranging application data, start with sorted or list.sort.

Document what a returned index refers to and whether sorting changes the original list. A technically correct index can still be used incorrectly if you apply it to a different ordering.

These small algorithms are easier to understand as functions because their inputs and results are explicit. The next lesson asks how their work changes when collections become larger.

PUT YOUR SKILLS TO WORK

Use the Section 4 challenges to practise these ideas independently. Work in your Python editor, predict results and keep a short test record.