1.2.6 Standard algorithms

Standard Searching Algorithms

Linear search checks each element of a list one at a time, from the beginning, until the target is found or the end of the list is reached. Works on any list — sorted or unsorted.

nums = [4, 7, 2, 9, 1, 5]
target = 9
found = False
for i in range(len(nums)):
    if nums[i] == target:
        found = True
        print("Found at index", i)
if not found:
    print("Not found")

Best case: target is the first element — 1 comparison.
Worst case: target is last or not present — n comparisons (n = list length).
Average case: n/2 comparisons.

Binary search works only on a sorted list. It repeatedly halves the search area: compare the target with the middle element; if the target is smaller, discard the right half; if larger, discard the left half. Repeat until found or the search area is empty.

nums = [1, 3, 5, 7, 9, 11, 13]   # must be sorted
target = 7
low = 0
high = len(nums) - 1
found = False
while low <= high and not found:
    mid = (low + high) // 2
    if nums[mid] == target:
        found = True
        print("Found at index", mid)
    elif nums[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
if not found:
    print("Not found")

Best case: target is the middle element — 1 comparison.
Worst case: approximately log₂(n) comparisons.
For a 1000-element list: linear search up to 1000 comparisons; binary search at most 10.

Standard Sorting Algorithms

Bubble sort repeatedly passes through the list, comparing adjacent pairs and swapping them if they are in the wrong order. Large values "bubble" to the end. Each complete pass places at least one more element in its final position.

nums = [5, 3, 8, 1, 4]
n = len(nums)
for pass_num in range(n - 1):
    for i in range(n - 1 - pass_num):
        if nums[i] > nums[i + 1]:
            # swap
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(nums)   # [1, 3, 4, 5, 8]

Trace: Pass 1 on [5, 3, 8, 1, 4]

Compare 5, 3 → swap → [3, 5, 8, 1, 4]
Compare 5, 8 → no swap → [3, 5, 8, 1, 4]
Compare 8, 1 → swap → [3, 5, 1, 8, 4]
Compare 8, 4 → swap → [3, 5, 1, 4, 8] — 8 is now in its final position

Number of passes: at most n-1 passes to guarantee sorted.
Comparisons per pass: reduces by 1 each pass as more elements settle.
Simple but inefficient for large lists compared to merge sort.

Merge sort uses a divide-and-conquer approach. It recursively splits the list in half until each sub-list has one element (which is trivially sorted), then merges the sub-lists back together in sorted order.

Worked example: merge sort [5, 3, 8, 1]

Split: [5, 3, 8, 1] → [5, 3] and [8, 1]
Split again: [5, 3] → [5] and [3]; [8, 1] → [8] and [1]
Merge [5] and [3]: compare 5 and 3 → [3, 5]
Merge [8] and [1]: compare 8 and 1 → [1, 8]
Merge [3,5] and [1,8]: 1<3 → take 1; 3<8 → take 3; 5<8 → take 5; take 8 → [1, 3, 5, 8]

More efficient than bubble sort for large lists.
Requires additional memory to hold the sub-lists during merging.
You are not expected to write full merge sort pseudocode — understanding how it works is sufficient at GCSE.

Comparison Summary

Algorithm	Type	Requires sorted?	Efficiency (worst)
Linear search	Searching	No	n comparisons
Binary search	Searching	Yes	log₂(n) comparisons
Bubble sort	Sorting	n/a	n² comparisons (approx)
Merge sort	Sorting	n/a	n log₂(n) comparisons

Key Takeaways

Linear search: check each element in turn — works on unsorted data, O(n) worst case.
Binary search: halve the search space each time — requires sorted data, much faster O(log n).
Bubble sort: repeatedly swap adjacent pairs — simple but slow for large lists.
Merge sort: split then merge — more efficient for large lists, uses extra memory.
Binary search cannot be used unless the list is already sorted.