OCR H446 · A Level Computer Science · ~16 min read
Notes
Video
Slides
Worksheet
Quiz
Searching Algorithms
Searching algorithms locate a target value within a collection. The two key algorithms at A Level are linear search and binary search.
Linear Search
Check each element in sequence until the target is found or the list is exhausted. Works on any list (sorted or unsorted).
linearSearch(list, target):
FOR i FROM 0 TO len(list)-1:
IF list[i] = target THEN RETURN i -- found at index i
RETURN -1 -- not found
Time complexity: O(n) best and average; O(n) worst. Simple but slow for large datasets.
Binary Search
Requires a sorted list. Repeatedly halves the search space by comparing the target to the middle element.
binarySearch(list, target):
low ← 0
high ← len(list) - 1
WHILE low ≤ high:
mid ← (low + high) DIV 2
IF list[mid] = target THEN RETURN mid
ELSE IF list[mid] < target THEN low ← mid + 1
ELSE high ← mid - 1
RETURN -1 -- not found-- Trace: find 7 in [1, 3, 5, 7, 9, 11, 13]-- low=0, high=6, mid=3 → list[3]=7 ✓ found at index 3-- (Lucky! Often takes multiple steps)-- Trace: find 9 in [1, 3, 5, 7, 9, 11, 13]-- Step 1: mid=3, list[3]=7 < 9 → low=4-- Step 2: mid=5, list[5]=11 > 9 → high=4-- Step 3: mid=4, list[4]=9 = 9 ✓ found
Time complexity: O(log n) — each step halves the remaining elements. Far superior to linear search for large sorted datasets.
Sorting Algorithms
Sorting rearranges a list into order (ascending or descending). Key algorithms: Bubble Sort, Insertion Sort, Merge Sort, Quicksort.
Bubble Sort
Repeatedly compare adjacent pairs, swapping if out of order. Each pass "bubbles" the largest unsorted element to its correct position.
bubbleSort(list):
n ← len(list)
FOR i FROM 0 TO n-2:
FOR j FROM 0 TO n-i-2:
IF list[j] > list[j+1] THEN
SWAP list[j] AND list[j+1]
-- Trace: [5, 3, 8, 1]-- Pass 1: [3,5,8,1] → [3,5,8,1] → [3,5,1,8] (8 in place)-- Pass 2: [3,5,1,8] → [3,1,5,8] (5 in place)-- Pass 3: [1,3,5,8] (done)
Time complexity: O(n²) average and worst. O(n) best case (already sorted with early termination flag). Simple but inefficient for large datasets.
Insertion Sort
Build a sorted portion from left to right. For each element, insert it into its correct position in the already-sorted left portion.
insertionSort(list):
FOR i FROM 1 TO len(list)-1:
key ← list[i]
j ← i - 1
WHILE j ≥ 0 AND list[j] > key:
list[j+1] ← list[j]
j ← j - 1
list[j+1] ← key
-- Trace: [5, 3, 8, 1]-- i=1: key=3, shift 5 right → [3,5,8,1]-- i=2: key=8, no shifts needed → [3,5,8,1]-- i=3: key=1, shift 8,5,3 right → [1,3,5,8]
Time complexity: O(n²) average and worst. O(n) best (already sorted). Efficient for small or nearly-sorted datasets. Stable (preserves relative order of equal elements).
Merge Sort
Divide and conquer: recursively split the list in half until single elements (base case), then merge sorted halves back together.
mergeSort(list):
IF len(list) ≤ 1 THEN RETURN list -- base case
mid ← len(list) DIV 2
left ← mergeSort(list[0..mid-1]) -- recursive calls
right ← mergeSort(list[mid..end])
RETURN merge(left, right)
merge(left, right): -- combine two sorted halves
result ← []
WHILE left and right not empty:
IF left[0] ≤ right[0]:
append left[0] to result; remove left[0]
ELSE:
append right[0] to result; remove right[0]
append remaining items to result
RETURN result
Time complexity: O(n log n) always (best, average, worst). Consistent and reliable. Disadvantage: O(n) extra space needed for merge step. Stable sort.
Quicksort
Choose a pivot, partition elements into those ≤ pivot (left) and those > pivot (right), then recursively sort each partition.
quickSort(list, low, high):
IF low < high:
p ← partition(list, low, high)
quickSort(list, low, p-1)
quickSort(list, p+1, high)
-- Time: O(n log n) average, O(n²) worst (bad pivot)-- Space: O(log n) average (stack frames)-- In-place (no extra array needed)-- Not stable
Complexity Comparison
Algorithm
Best
Average
Worst
Space
Stable?
Linear search
O(1)
O(n)
O(n)
O(1)
N/A
Binary search
O(1)
O(log n)
O(log n)
O(1)
N/A
Bubble sort
O(n)
O(n²)
O(n²)
O(1)
Yes
Insertion sort
O(n)
O(n²)
O(n²)
O(1)
Yes
Merge sort
O(n log n)
O(n log n)
O(n log n)
O(n)
Yes
Quicksort
O(n log n)
O(n log n)
O(n²)
O(log n)
No
Exam tip: Binary search requires a sorted list. You must halve the search space each step. The number of steps required is at most log₂(n). For n=1000: log₂(1000) ≈ 10 steps. You will be asked to trace a binary search — always show low, high, and mid values at each step.
Exam tip: Merge sort has O(n log n) always. Quicksort averages O(n log n) but degrades to O(n²) with a bad pivot. In exams: if asked which is better for guaranteed performance, say Merge sort. If asked about space efficiency, say Quicksort (in-place, O(log n) space).
⚠ Common Mistakes
Using binary search on an unsorted list — it will give wrong results. Always check for the sorted precondition.
Counting the wrong number of passes in bubble sort — n elements need at most n−1 passes, not n.
Confusing insertion sort with selection sort — insertion sort inserts into the sorted left portion; selection sort finds the minimum each time.
Saying quicksort is always O(n log n) — in the worst case (sorted input with first element as pivot) it is O(n²).
✓ Notes completed!
▶
Video coming soon
Click to advance · Arrow keys also work
Click slide or press arrow keys to navigate
✍
Worksheet — 1.4.2h Searching and Sorting
8 questions · 22 marks · instantly marked
Q1Trace binary search for target=14 in the sorted list [2, 5, 8, 11, 14, 18, 22]. Show the value of low, high, and mid at each step.[4 marks]
✓ Mark scheme
Step 1: low=0, high=6, mid=3, list[3]=11, 11<14 → low=4 [1]. Step 2: low=4, high=6, mid=5, list[5]=18, 18>14 → high=4 [1]. Step 3: low=4, high=4, mid=4, list[4]=14, 14=14 ✓ found at index 4 [1]. Correct final answer: index 4 [1].
Q2State the precondition required before applying binary search. What is its time complexity?[2 marks]
✓ Mark scheme
Precondition: the list must be sorted (in ascending or descending order) [1]. Time complexity: O(log n) — each step halves the remaining search space [1].
Q3Trace one full pass of bubble sort on [7, 2, 9, 4], showing each swap. What is the state of the list after this pass?[3 marks]
✓ Mark scheme
Compare 7 and 2: swap → [2,7,9,4] [1]. Compare 7 and 9: no swap → [2,7,9,4]. Compare 9 and 4: swap → [2,7,4,9] [1]. After pass 1: [2,7,4,9] — the largest element (9) has bubbled to its correct position [1].
Q4Trace insertion sort on [5, 3, 8, 1] showing the state after inserting each element.[4 marks]
Q5Explain how merge sort works using divide and conquer. State its time complexity in all cases.[4 marks]
✓ Mark scheme
Divide: recursively split the list in half until each sub-list has size 1 (base case — single element is already sorted) [1]. Conquer: repeatedly merge pairs of sorted sub-lists into a larger sorted list by comparing front elements and taking the smaller [1]. Combine: the merging process produces progressively larger sorted sub-lists until the whole list is sorted [1]. Time complexity: O(n log n) in all cases — best, average, and worst. The log n factor is the number of split levels; n factor is the work done merging at each level [1].
Q6Compare merge sort and quicksort in terms of: (i) worst-case time complexity, (ii) space complexity, (iii) stability.[3 marks]
✓ Mark scheme
(i) Worst-case time: merge sort O(n log n) always; quicksort O(n²) with a bad pivot choice (e.g. sorted input with first element as pivot) [1]. (ii) Space: merge sort O(n) extra space for the merged array; quicksort O(log n) average (stack frames only — in-place) [1]. (iii) Stability: merge sort is stable (equal elements preserve relative order); quicksort is generally not stable [1].
Q7Why is binary search more efficient than linear search for a large sorted dataset? Give a numerical example to illustrate.[3 marks]
✓ Mark scheme
Binary search is O(log n) vs linear search O(n) [1]. Binary search halves the search space each step — for n=1,000,000: linear search needs up to 1,000,000 comparisons, binary search needs at most log₂(1,000,000) ≈ 20 comparisons [1]. For large datasets, this difference is enormous — but binary search requires the list to be sorted first [1].
Q8State which sorting algorithm you would choose for each scenario, with justification: (a) a nearly-sorted list of 50 items, (b) a large unsorted dataset of 1 million items where consistent performance is critical.[4 marks]
✓ Mark scheme
(a) Insertion sort — for nearly-sorted small lists it runs close to O(n) because few shifts are needed; it is very efficient when elements are mostly in order [2]. (b) Merge sort — guaranteed O(n log n) in all cases, including worst case; quicksort risks O(n²) with bad pivots on large datasets; merge sort is stable and consistent [2]. Accept quicksort (b) if student notes use of random pivot or median-of-three to avoid worst case.
Topic Quiz
1 of 15
You scored
out of 15
🎯
Mini Test — 1.4.2h
10 questions · 10 marks · 10 minutes
5 MCQ + 5 short answer
⏱10:00
10 marks
Section A — Multiple Choice
Q1What is the time complexity of binary search?
Q2Which sorting algorithm guarantees O(n log n) in all cases?
Q3What is the worst-case time complexity of quicksort?
Q4After one pass of bubble sort on [4, 1, 7, 3], which element is guaranteed to be in its correct position?
Q5Which algorithm is most efficient for a nearly-sorted list of 20 items?
Section B — Short Answer
Q6State the precondition for binary search and explain why it is necessary.
Mark schemePrecondition: the list must be sorted. Necessary because binary search works by comparing the target with the middle element and eliminating half the list. If unsorted, eliminating half the elements may discard the target — the algorithm would give incorrect results. [1 mark]
Q7What is the maximum number of steps binary search needs for a list of 128 elements?
Mark schemeMaximum steps = log₂(128) = 7. After each step the search space halves: 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. Seven halvings. General formula: ⌈log₂(n)⌉ steps. [1 mark]
Q8What is a "stable" sorting algorithm? Is merge sort stable?
Mark schemeStable sort: if two elements have equal values, a stable sort preserves their original relative order (the one that appeared first in the input remains first in the output). Yes, merge sort is stable — during the merge step, when two elements are equal we always pick from the left half first, preserving order. [1 mark]
Q9Why does merge sort require O(n) extra space?
Mark schemeDuring the merge step, a temporary array of size n is needed to hold the merged result before copying it back. Unlike bubble/insertion sort (which swap in-place), merge sort cannot merge two sorted halves into the same space without an auxiliary buffer — elements would be overwritten. [1 mark]
Q10State the best-case time complexity of bubble sort and describe the input that achieves it.
Mark schemeBest case: O(n). Input: an already-sorted list. With an early-termination flag (stop if no swaps occurred in a pass), bubble sort detects the list is sorted in just one pass with n-1 comparisons and zero swaps → O(n). Without the flag, it is O(n²) even for a sorted list. [1 mark]