CAIE 9618 · Paper 2 · Topic 2.1.3

Searching
Algorithms

Linear Search · Binary Search · Trace Tables · Efficiency Comparison

CSZone Cambridge International AS & A Level Computer Science 9618

Linear Search

Check Every Element in Order

A linear search sequentially checks each element of a list until the target is found or the end is reached. Works on unsorted or sorted data.

DECLARE found : BOOLEAN
DECLARE i : INTEGER
found <- FALSE
i <- 1
WHILE i <= n AND NOT found DO
IF list[i] = target THEN
found <- TRUE
ELSE
i <- i + 1
ENDIF
ENDWHILE
IF found THEN OUTPUT i ELSE OUTPUT "-1" ENDIF

COMPLEXITY

Best case: O(1) — target is first element
Average: O(n/2) ≈ O(n)
Worst case: O(n) — target at end or not found

WHEN TO USE

List is unsorted. List is small. Items may not exist. Simplest to implement. Works on linked lists (no random access needed).

Binary Search

Divide and Conquer

Binary search works on sorted arrays only. It repeatedly halves the search space by comparing the target to the middle element.

lo <- 1, hi <- n, found <- FALSE
WHILE lo <= hi AND NOT found DO
mid <- (lo + hi) DIV 2
IF list[mid] = target THEN
found <- TRUE
ELSE IF target < list[mid] THEN
hi <- mid - 1
ELSE
lo <- mid + 1
ENDIF
ENDWHILE

COMPLEXITY

Best case: O(1) — target is the middle
Worst case: O(log₂ n)
1024 elements → max 10 comparisons!

REQUIREMENT

Must be sorted first. Requires random access (arrays, not linked lists). More complex to implement but vastly more efficient for large datasets.

Binary Search Trace

Worked Example: Find 42

Array: [5, 12, 18, 25, 30, 42, 56, 70, 88, 99] — sorted, n=10, target=42

lo	hi	mid	list[mid]	Action
1	10	5	30	30 < 42 → lo = mid+1 = 6
6	10	8	70	70 > 42 → hi = mid-1 = 7
6	7	6	42	Found! Return index 6

Only 3 comparisons needed to find 42 in a 10-element array. Linear search would need up to 6 comparisons for this item.

Comparison

Linear vs Binary Search

Property	Linear Search	Binary Search
Requires sorted data?	No	Yes
Best case	O(1)	O(1)
Worst case	O(n)	O(log n)
Works on linked lists?	Yes	No (needs random access)
Implementation complexity	Simple	Moderate
Best for small datasets?	Yes	Overkill
Best for large datasets?	Poor	Excellent

Exam Practice

Cambridge-style questions

Question 1

The array Data contains 1024 sorted integers. State the maximum number of comparisons required by (i) a linear search and (ii) a binary search to determine that a target value is not in the array.

4 marks

2 marks

(i) Linear search: 1024 comparisons — must check every element to confirm the target is absent

2 marks

(ii) Binary search: log₂(1024) = 10 comparisons — each comparison halves the remaining search space; after 10 halvings the space is empty, confirming absence

Common Mistakes

Don't lose easy marks

1

Applying binary search to unsorted data — this is the most common mistake. Binary search only works correctly on sorted data. Always state this precondition when recommending binary search.

2

Calculating mid incorrectly — mid should be (lo + hi) DIV 2 (integer division). Do not use (lo + hi) / 2 without truncating, as non-integer indices are invalid. In the exam, show the DIV calculation explicitly.

3

Saying binary search is "always better" — for small lists or when data is frequently changing (requiring re-sorting), linear search may be more practical. Always qualify your recommendation with the context.

Topic Summary — 2.1.3

What You Need to Know

LINEAR SEARCH

Check each element sequentially
Works on unsorted data
O(n) worst case · Simple to implement

BINARY SEARCH

Requires sorted array
mid = (lo + hi) DIV 2
O(log n) worst case
1024 elements → max 10 comparisons

CSZone

Next Video

2.1.4

Sorting Algorithms

Bubble Sort · Insertion Sort · Merge Sort

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools