Show understanding of linear and binary searching methods

19.1 Algorithms – Searching Methods (Cambridge International AS & A Level Computer Science 9618)

Learning Outcomes

• Explain the purpose of searching algorithms and the situations in which they are used (AO1).
• Analyse and compare the time‑ and space‑complexities of linear and binary search, including best, average and worst cases (AO2).
• Design, implement (pseudocode), test and evaluate linear and binary search solutions, including recursive versions and handling of edge cases (AO3).

Syllabus Alignment Checklist

Quick‑Reference Checklist for Aligning Your Lecture Notes with the Cambridge AS & A‑Level Computer Science (9618) Syllabus (2026)

1. Linear Search (Sequential Scan)

1.1 Concept

Linear search examines each element of a collection in order until the target value is found or the end of the collection is reached. It works on any data set – sorted or unsorted.

1.2 Pseudocode (Iterative)

function linearSearch(arr, target):
// arr – one‑dimensional array, 0‑based indexing
for i ← 0 to length(arr)‑1 do
if arr[i] = target then
return i          // index of first occurrence
return -1                 // target not present

1.3 Recursive Version (AO3 – recursion)

function linearSearchRec(arr, target, i):
if i = length(arr) then
return -1                 // reached end – not found
if arr[i] = target then
return i
return linearSearchRec(arr, target, i+1)

1.4 Complexity Summary

1.5 Trace Table (example)

Search for 23 in L = [5, 12, 23, 7, 19]

1.6 Edge‑Case Handling (AO3)

• Empty array: loop never executes → return –1.
• Target absent: loop runs to length‑1 → return –1.
• Duplicate values: returns the index of the first occurrence.

2. Binary Search (Divide‑and‑Conquer)

2.1 Preconditions

• The array must be sorted in non‑decreasing order.
• Indices are 0‑based; low points to the first candidate, high to the last.

2.2 Pseudocode (Iterative)

function binarySearch(arr, target):
low  ← 0
high ← length(arr)‑1
while low ≤ high do
mid ← floor((low + high) / 2)
if arr[mid] = target then
return mid
else if arr[mid] < target then
low ← mid + 1
else
high ← mid – 1
return -1

2.3 Recursive Version (AO3 – recursion)

function binarySearchRec(arr, target, low, high):
if low > high then
return -1                     // not found
mid ← floor((low + high) / 2)
if arr[mid] = target then
return mid
else if arr[mid] < target then
return binarySearchRec(arr, target, mid+1, high)
else
return binarySearchRec(arr, target, low, mid‑1)

2.4 Complexity Summary

2.5 Trace Table (example)

Search for 23 in S = [5, 7, 12, 19, 23, 31, 42]

2.6 Edge‑Case Handling

• Empty array: low = 0, high = -1 → loop condition false → return –1.
• Target absent: interval shrinks until low > high → return –1.
• Duplicate values: the basic algorithm may return any matching index. A modified version can continue searching left‑ or right‑hand side to locate the first or last occurrence.

3. Algorithm Selection – When to Use Which Search?

Additional Searching Techniques (syllabus breadth)

• Hash‑based lookup: average‑case O(1) search using a hash table (relevant for A‑Level “Algorithm design and problem‑solving”).
• Interpolation search: improves binary search for uniformly distributed numeric data; average complexity O(log log n).
• These techniques are mentioned in the syllabus but are not required for the core 19.1 assessment; they can be introduced as extension activities.

4. Testing Plan (AO3)

For each algorithm, students should produce a concise test plan covering the following categories:

1. Normal case: target present in the middle of the array.
2. Boundary cases:

   • Target is the first element.
   • Target is the last element.

3. Edge cases:

   • Empty array.
   • Target not present.
   • Array containing duplicate values.

4. Performance check (optional): count comparisons for increasing n to confirm O(n) vs O(log n) behaviour.

Sample Test Table – Binary Search

5. Sample Exam Questions & Marking Guidance

Question 1 – Linear Search Trace

Prompt: Given the array A = [14, 7, 19, 3, 11], trace the execution of linear search to find the value 3. Show the values of the loop index i and the comparison result at each iteration, and state the final index returned.

Mark Scheme (6 marks):

1. Initialisation of i = 0 (1 mark)
2. Comparison A[0]=14 ≠ 3 – continue (1 mark)
3. Comparison A[1]=7 ≠ 3 – continue (1 mark)
4. Comparison A[2]=19 ≠ 3 – continue (1 mark)
5. Comparison A[3]=3 = 3 – found (1 mark)
6. Return index 3 (1 mark)

Question 2 – Binary Search Design

Prompt: Write pseudocode for a recursive binary search that returns the index of the first occurrence of target in a sorted array arr. Include a brief comment on its time‑complexity.

Mark Scheme (8 marks):

• Correct base case (low > high) – 1 mark
• Correct calculation of mid – 1 mark
• Equality test and return of mid – 1 mark
• Recursive call for arr[mid] < target – 1 mark
• Recursive call for arr[mid] > target – 1 mark
• Additional step to continue searching left side for first occurrence (e.g., check mid‑1 when a match is found) – 2 marks
• Complexity comment “O(log n) time, O(log n) stack space” – 1 mark

Question 3 – Algorithm Choice (AO2)

Prompt: A school database stores 12 000 student IDs in a sorted array. The system must answer 10 000 look‑up queries per day. Which searching algorithm would you recommend and why? (4 marks)

Mark Scheme (4 marks):

1. Identify binary search as the appropriate algorithm (1 mark).
2. Explain that the data is already sorted, satisfying the pre‑condition (1 mark).
3. State that binary search’s O(log n) time makes it far faster than linear search for 12 000 items, especially with many daily queries (1 mark).
4. Note that the iterative version uses O(1) extra space, suitable for the given memory constraints (1 mark).