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 1CP2Searching and Sorting Algorithms
Key facts
Searching algorithms
Linear search — starts at first item, checks each in turn until found or end reached. Works on unsorted data. O(n) — slow for large lists.
Binary search — requires sorted data. Starts at middle. If target > middle: search right half. If target < middle: search left half. Repeat. O(log n) — much faster for large lists.
Divide and conquer: Binary search is a divide and conquer algorithm. Linear search is NOT.
Jun 2024 Q1(f)(i): "Binary search — is a divide and conquer algorithm. Bubble sort — is not a divide and conquer algorithm."
Sorting algorithms
Bubble sort — compares adjacent pairs, swaps if out of order, repeats until no swaps in a pass. Simple but slow O(n²). NOT divide and conquer.
Merge sort — divides list in half recursively, sorts each half, merges back together. O(n log n) — faster than bubble for large lists. IS divide and conquer.
Key exam point: binary search requires a sorted list — bubble/merge sort are how you get it sorted first.
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
Exam questions — 4 questions · 11 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?