Linear search, binary search, bubble sort, merge sort. Jun 2024 Q1(f) and Jun 2023 Q4(d) both tested searches. Key: compare their efficiency.
—
Best score
—
Last attempt
Best attempt progress
0
XP earned
Watch first — Craig 'n' Dave
Craig 'n' Dave · Edexcel 1CP2Bubble sort (7:37)
Craig 'n' Dave · Edexcel 1CP2Merge sort (8:12)
Craig 'n' Dave · Edexcel 1CP2Linear search (5:59)
Craig 'n' Dave · Edexcel 1CP2Binary search (10:01)
Craig 'n' Dave · Edexcel 1CP2Algorithm efficiency (14:11)
Key facts
Searching algorithms — fill in the table
Algorithm
Description
Linear search
Binary search
Divide and conquer
Exam wording
Sorting algorithms — fill in the table
Algorithm
Description
Bubble sort
Merge sort
Key exam point
Why binary search is faster
Each comparison eliminates HALF the remaining data
For a list of 1,000 items: linear search may need 1,000 comparisons; binary search needs at most 10
For a list of 1,000,000 items: binary search needs at most 20 comparisons
Trade-off: binary search requires the list to be sorted first — this has its own cost
The four standard algorithms (spec 1.2.6) — fill in the table
Algorithm
How it works
Linear search
Binary search
Bubble sort
Merge sort
Efficiency (spec 1.2.7)
Worked examples
Binary search for 23 in [2, 5, 8, 12, 16, 23, 38]: the middle is 12, which is less than 23, so keep [16, 23, 38]; the middle is 23, found.
Merge sort [6, 3, 8, 1]: split to [6, 3] and [8, 1], then to single items, merge to [3, 6] and [1, 8], then merge to [1, 3, 6, 8].
Bubble sort [5, 2, 4, 1], pass 1: 5 and 2 swap, 5 and 4 swap, 5 and 1 swap, giving 2 4 1 5. The largest item has bubbled to the end.
Bubble sort on [5, 2, 4, 1]
Pass 1: 5,2 swap -> 2 5 4 1 | 5,4 swap -> 2 4 5 1 | 5,1 swap -> 2 4 1 5
Pass 2: 2,4 no swap | 4,1 swap -> 2 1 4 5
Pass 3: 2,1 swap -> 1 2 4 5
Pass 4: no swaps, so the list is sorted: 1 2 4 5
Exam questions — 7 questions · 13 marks · from real 1CP2 past papers
1 markDivide and conquer1CP2 Jun 2024 Q1(f)(i) style
Which search algorithm is a divide and conquer algorithm?
A Linear search
B Binary search
C Bubble sort
D Sequential search
2 marksBinary search steps1CP2 Jun 2023 Q4(d) style
Describe how a binary search finds a target value in a sorted list. (2 marks — linked description)
Hint: Start → find middle → compare → eliminate half → repeat. This needs to be a linked description — not just a list.
+20 XP
2 marksBubble sort efficiency1CP2 Jun 2024 Q1(f)(ii) style
A sorting algorithm runs on a small list and executes quickly. Explain why this does not mean it will execute quickly on a very large list. (2 marks)
Hint: Link: small list → few comparisons → fast. Large list → many more comparisons → slow. The key is the relationship between list size and number of comparisons.
+20 XP
1 markBinary search requirement1CP2 style
What is the prerequisite for using a binary search?
A The list must contain only integers
B The list must have fewer than 100 items
C The list must be sorted in order
D The list must be stored in a 2D array
1 markLinear search1CP2 style
Which search algorithm can be used on a list that is NOT sorted?
A Binary search
B Linear search
C Merge search
D Bubble search
3 marksBubble sort pass1CP2 style
Show the list [4, 2, 5, 1] after the first pass of a bubble sort (ascending order). Show each comparison. (3 marks)
Hint: Compare neighbours from the left and swap when the left one is bigger.
+30 XP
3 marksMerge sort1CP2 style
Describe how a merge sort would sort the list [7, 3, 5, 1] into ascending order. (3 marks)
Hint: Split down to single items, then merge pairs in order.