2.4.1 Searching Algorithms — Linear & Binary Search
Cambridge 9618 · International A Level Computer Science · ~13 min read
Notes
Video
Slides
Quiz
Worksheet
Linear Search
A linear search (also called sequential search) checks each element of an array one by one, from first to last, until the target is found or the entire array has been checked.
How Linear Search Works
Start at index 1 (or 0 — check what convention is used)
Compare each element with the target value
If match found → return the index (or set a found flag)
If no match after checking all elements → report not found
Works on unsorted and sorted arrays
Linear Search — Visualised
Searching for 47 in array [12, 5, 47, 3, 88, 21]
12[1]
5[2]
47[3] ✓
3[4]
88[5]
21[6]
Checked: [1]=12 ✗, [2]=5 ✗, [3]=47 ✓ — found at index 3 after 3 comparisons
Linear Search — Cambridge 9618 Pseudocode
FUNCTION LinearSearch(arr : ARRAY[1:6] OF INTEGER, target : INTEGER) RETURNS INTEGER DECLARE i : INTEGER FOR i ← 1TO6 IF arr[i] = target THEN RETURN i // found — return index ENDIF NEXT i RETURN-1// not found ENDFUNCTION
Linear Search — Complexity
Best case: O(1) — target is the first element. Worst case: O(n) — target is last or not present; must check all n elements. Average case: O(n/2) ≈ O(n)
Binary Search
A binary search works on a sorted array only. It repeatedly halves the search space by comparing the target to the middle element. Much faster than linear search for large datasets.
How Binary Search Works
Requires the array to be sorted (ascending or descending)
Set Low = 1 (first index) and High = n (last index)
Calculate Mid = (Low + High) DIV 2
If arr[Mid] = target → found at Mid
If arr[Mid] < target → target is in upper half → Low = Mid + 1
If arr[Mid] > target → target is in lower half → High = Mid - 1
Repeat until found or Low > High (not found)
Binary Search — Visualised
Searching for 33 in sorted array [3, 12, 21, 33, 47, 88, 95]
FUNCTION BinarySearch(arr : ARRAY[1:7] OF INTEGER, target : INTEGER) RETURNS INTEGER DECLARE Low, High, Mid : INTEGER
Low ← 1
High ← 7 WHILE Low <= High DO
Mid ← (Low + High) DIV2 IF arr[Mid] = target THEN RETURN Mid ELSE IF arr[Mid] < target THEN
Low ← Mid + 1 ELSE
High ← Mid - 1 ENDIF ENDIF ENDWHILE RETURN-1// not found ENDFUNCTION
Binary Search — Complexity
Best case: O(1) — target is the middle element on first pass. Worst case: O(log₂ n) — array is halved each pass. For n=1024, only 10 comparisons needed.
Linear Search vs Binary Search — Comparison
Feature
Linear Search
Binary Search
Array must be sorted?
No — works on any array
Yes — must be sorted first
Best case
O(1) — first element
O(1) — middle element
Worst case
O(n)
O(log₂ n)
100-element array, worst case
100 comparisons
7 comparisons
1,000,000 elements, worst case
1,000,000 comparisons
~20 comparisons
Implementation complexity
Simple
More complex
Use when
Small arrays, unsorted data, single lookup
Large sorted arrays, repeated searches
Exam tip: Cambridge 9618 exam questions often ask you to trace through a binary search. Always show the values of Low, High, and Mid at each step in a trace table. Key formula: Mid = (Low + High) DIV 2. Remember — DIV gives the integer result. For sorted array [1,2,3,4,5,6,7], Mid=(1+7) DIV 2 = 4.
The key requirement: Binary search REQUIRES a sorted array. If an exam question says the array is unsorted, you MUST use linear search (or sort first, then binary search). Applying binary search to an unsorted array gives wrong results.
⚠️ Common Mistakes
Using binary search on an unsorted array — this will give wrong results
Calculating Mid as (Low + High) / 2 instead of (Low + High) DIV 2 — always use DIV for integer index
Forgetting to update Low/High after each pass — the loop would be infinite
Stopping binary search when Low = High without checking arr[Mid] = target at that point
Claiming binary search has O(n) complexity — it's O(log₂ n), which is far better
Confusing the not-found condition: loop ends when Low > High (not Low = High)
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 2.4.1 Searching Algorithms
8 questions · Cambridge 9618 standard
Q1Describe how a linear search works. State the worst case number of comparisons needed to search a list of 50 items.[3]
✅ Mark scheme
Each element is compared with the target in sequence from first to last [1]; the search stops when the target is found or the end of the list is reached [1]; worst case = 50 comparisons (item not present or last element) [1].
Q2State one advantage and one disadvantage of binary search compared to linear search.[2]
✅ Mark scheme
Advantage: Binary search is much faster for large sorted arrays — O(log₂ n) vs O(n) [1]; Disadvantage: The array must be sorted before binary search can be used; linear search works on unsorted arrays [1].
Q3Perform a binary search for the value 72 in the sorted array [4, 15, 28, 42, 59, 72, 88, 95]. Show the values of Low, Mid, and High at each step in a trace table.[5]
✅ Mark scheme
Low=1, High=8 [1]; Pass 1: Mid=(1+8) DIV 2=4, arr[4]=42 < 72, Low=5 [1]; Pass 2: Mid=(5+8) DIV 2=6, arr[6]=72 = 72 → Found at index 6 [1]. Low/High correctly updated [1]; correct use of DIV [1].
Q4A programmer wants to search for a student's name in an unsorted list of 1000 names. Which search algorithm should they use and why?[2]
✅ Mark scheme
Linear search should be used [1]; because the list is unsorted and binary search requires a sorted array; alternatively, they could sort the list first then use binary search but this adds overhead [1].
Q5Write Cambridge 9618 pseudocode for a linear search that returns -1 if the target is not found, using array A[1:10] and searching for target.[5]
✅ Mark scheme
FUNCTION/PROCEDURE header with appropriate parameters [1]; DECLARE i : INTEGER [1]; FOR i ← 1 TO 10 [1]; IF A[i] = target THEN RETURN i ENDIF [1]; NEXT i; RETURN -1 [1].
Q6A sorted array has 1,048,576 (2²⁰) elements. What is the maximum number of comparisons needed by a binary search? Show your working.[2]
✅ Mark scheme
Binary search is O(log₂ n) [1]; log₂(1,048,576) = log₂(2²⁰) = 20 comparisons maximum [1].
Q7A program uses a WHILE loop to read integers from a user until they enter 0, then outputs the total. Write the pseudocode and identify the loop condition, body, and termination condition.[5]
✅ Mark scheme
DECLARE total, num : INTEGER; total ← 0 — 1 mark; INPUT num — before loop — 1 mark; WHILE num ≠ 0 DO (condition) — 1 mark; total ← total + num; INPUT num (body) — 1 mark; ENDWHILE; OUTPUT total — 1 mark.
Q8Compare FOR loops and REPEAT…UNTIL loops. Give one situation where a REPEAT…UNTIL loop is more appropriate than a FOR loop and explain why.[4]
✅ Mark scheme
FOR: fixed known number of iterations — 1 mark; REPEAT…UNTIL: executes body at least once, condition checked after — 1 mark; suitable when input must be validated because at least one input attempt is needed — 1 mark; e.g. REPEAT INPUT password UNTIL password = "correct" ensures prompt appears before validation — 1 mark.
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 6
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 2.4.1 Searching Algorithms
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1What is the worst-case time complexity of a linear search on n elements?
Q2Binary search requires the data to be:
Q3Binary search on a sorted array of 128 elements. What is the maximum number of comparisons?
Q4In binary search, after calculating Mid, arr[Mid] is greater than the target. What happens next?
Q5When does a binary search report "not found"?
Section B — Short Answer [5 marks]
Q6State the main requirement for binary search and explain why it cannot be used without it.
Mark schemeThe array must be sorted [1]; binary search works by halving the search space — if the array is not sorted, comparing the target with the middle element gives no information about which half the target might be in, so the algorithm would give incorrect results [1].
Q7Perform a binary search for value 10 in [2, 5, 8, 10, 15, 20]. Show Low, Mid, High at each step.
Mark schemeLow=1, High=6 [1]; Pass 1: Mid=(1+6) DIV 2=3, arr[3]=8 < 10, Low=4 [1]; Pass 2: Mid=(4+6) DIV 2=5, arr[5]=15 > 10, High=4 [1]; Pass 3: Mid=(4+4) DIV 2=4, arr[4]=10=10, Found at index 4 [1].
Q8Give one advantage of linear search over binary search.
Mark schemeAny one of: Linear search works on unsorted data [1]; it is simpler to implement [1]; it is equally fast for very small arrays [1].
Q9In Cambridge 9618 pseudocode, how is the midpoint calculated in binary search?
Mark schemeMid ← (Low + High) DIV 2 [1]. Must use DIV (integer division) not / (which gives a REAL result and cannot be used as an array index) [1].
Q10A linear search checks each element in turn. For an array of 1000 items, how many comparisons are needed in the worst case? How does this compare to binary search?
Mark schemeLinear search: 1000 comparisons worst case [1]; binary search: log₂(1000) ≈ 10 comparisons worst case [1] — binary search is dramatically more efficient for large datasets.