Paper 2 Search and Sort Answers

These answers correspond to Paper 2 Search and Sort Drills.

Verification note: the model snippets in this file were executed locally as a combined Python script on 2026-07-09.

Answer 1: Linear Search Function

def linear_search(values, target):
    for index, value in enumerate(values):
        if value == target:
            return index
    return -1
 
 
print(linear_search([12, 5, 9, 21], 9))
print(linear_search([12, 5, 9, 21], 7))

Expected output:

2
-1

Mark points:

• loops through the list with access to indexes;
• compares each value with target;
• returns the index when found;
• returns -1 after the loop when absent;
• shows both required test calls and outputs.

Common weak answer:

• returning True or the target value instead of the index.

Answer 2: Linear Search Count

def count_until_found(values, target):
    checked = 0
    for value in values:
        checked = checked + 1
        if value == target:
            return checked
    return checked
 
 
print(count_until_found([6, 3, 8, 2], 8))
print(count_until_found([6, 3, 8, 2], 5))

Expected output:

3
4

Mark points:

• initialises a counter;
• increments the counter for each inspected item;
• stops and returns when the target is found;
• returns the full count when the target is absent;
• shows the required tests.

Answer 3: Binary Search Function

def binary_search(values, target):
    low = 0
    high = len(values) - 1
 
    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        if target > values[mid]:
            low = mid + 1
        else:
            high = mid - 1
 
    return -1
 
 
print(binary_search([4, 9, 15, 21, 28, 34, 42], 28))
print(binary_search([4, 9, 15, 21, 28, 34, 42], 20))

Expected output:

4
-1

Mark points:

• initialises low and high correctly;
• uses while low <= high;
• calculates mid with integer division;
• returns mid when the target is found;
• updates low to mid + 1 when the target is larger;
• updates high to mid - 1 when the target is smaller;
• returns -1 after the loop;
• shows both required outputs.

Common weak answer:

• using low = mid or high = mid, which can repeat the same middle index.

Answer 4: Binary Search With Comparison Count

def binary_search_count(values, target):
    low = 0
    high = len(values) - 1
    comparisons = 0
 
    while low <= high:
        mid = (low + high) // 2
        comparisons = comparisons + 1
        if values[mid] == target:
            return mid, comparisons
        if target > values[mid]:
            low = mid + 1
        else:
            high = mid - 1
 
    return -1, comparisons
 
 
print(binary_search_count([2, 5, 8, 11, 14, 17, 20], 17))
print(binary_search_count([2, 5, 8, 11, 14, 17, 20], 7))

Expected output:

(5, 2)
(-1, 3)

Mark points:

• initialises the comparison counter;
• increments it once per middle-value comparison;
• returns (index, comparisons) when found;
• returns (-1, comparisons) when absent;
• uses correct binary-search boundary updates.

Answer 5: Bubble Sort Function

def bubble_sort(values):
    result = values[:]
    n = len(result)
 
    for pass_number in range(n - 1):
        for index in range(n - 1 - pass_number):
            if result[index] > result[index + 1]:
                result[index], result[index + 1] = result[index + 1], result[index]
 
    return result
 
 
data = [6, 2, 9, 1, 5]
print(bubble_sort(data))
print(data)

Expected output:

[1, 2, 5, 6, 9]
[6, 2, 9, 1, 5]

Mark points:

• copies the input list before sorting;
• compares adjacent values;
• swaps adjacent out-of-order values;
• reduces the inner loop range after each pass;
• returns the sorted copy;
• leaves the original list unchanged;
• shows both required outputs.

Answer 6: Optimised Bubble Sort

def bubble_sort_passes(values):
    result = values[:]
    n = len(result)
    passes = 0
 
    for pass_number in range(n - 1):
        swapped = False
        for index in range(n - 1 - pass_number):
            if result[index] > result[index + 1]:
                result[index], result[index + 1] = result[index + 1], result[index]
                swapped = True
        passes = passes + 1
        if not swapped:
            break
 
    return passes
 
 
print(bubble_sort_passes([1, 2, 3, 4]))
print(bubble_sort_passes([4, 3, 2, 1]))

Expected output:

1
3

Mark points:

• uses a swapped flag;
• counts each complete pass;
• detects a no-swap pass;
• stops early when already sorted;
• handles a reverse-ordered list correctly.

Answer 7: Insertion Sort Function

def insertion_sort(values):
    result = values[:]
 
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
 
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position = position - 1
 
        result[position + 1] = current
 
    return result
 
 
print(insertion_sort([7, 3, 5, 2]))

Expected output:

[2, 3, 5, 7]

Mark points:

• copies the input list so the original is not modified;
• starts from the second item;
• stores the current item before shifting;
• shifts larger sorted-section values right;
• inserts the current item in the open position;
• returns the sorted list.

Answer 8: Merge Two Sorted Lists

def merge_sorted(left, right):
    result = []
    left_index = 0
    right_index = 0
 
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index = left_index + 1
        else:
            result.append(right[right_index])
            right_index = right_index + 1
 
    result.extend(left[left_index:])
    result.extend(right[right_index:])
    return result
 
 
print(merge_sorted([2, 6, 9], [1, 5, 10, 12]))

Expected output:

[1, 2, 5, 6, 9, 10, 12]

Mark points:

• keeps separate indexes for left and right;
• compares the first unmerged values;
• appends the smaller value;
• advances the correct index;
• appends leftover values after one list is exhausted;
• returns the merged sorted list.

Answer 9: Sort Records by Key

def sort_by_score(records):
    result = [record[:] for record in records]
 
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
 
        while position >= 0 and result[position][1] < current[1]:
            result[position + 1] = result[position]
            position = position - 1
 
        result[position + 1] = current
 
    return result
 
 
records = [["Nora", 64], ["Ivan", 82], ["Mina", 75], ["Omar", 82]]
print(sort_by_score(records))

Expected output:

[['Ivan', 82], ['Omar', 82], ['Mina', 75], ['Nora', 64]]

Mark points:

• sorts using the score field at index 1;
• uses descending comparison;
• keeps equal-score records stable by not shifting equal scores;
• returns a new list, so the original records are not modified;
• shows the expected output.

Answer 10: Search After Sorting

def insertion_sort(values):
    result = values[:]
    for index in range(1, len(result)):
        current = result[index]
        position = index - 1
        while position >= 0 and result[position] > current:
            result[position + 1] = result[position]
            position = position - 1
        result[position + 1] = current
    return result
 
 
def binary_search(values, target):
    low = 0
    high = len(values) - 1
    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        if target > values[mid]:
            low = mid + 1
        else:
            high = mid - 1
    return -1
 
 
values = [31, 12, 44, 18, 27, 9]
sorted_values = insertion_sort(values)
index = binary_search(sorted_values, 27)
print(sorted_values)
print(index)

Expected output:

[9, 12, 18, 27, 31, 44]
3

Mark points:

• stores the original list;
• sorts using the student’s own insertion sort;
• searches the sorted list, not the original unsorted list;
• uses binary search with correct boundary updates;
• prints the sorted list;
• prints the correct index of 27.