1.2b Searching Algorithms — Edexcel 1CP2

Searching Algorithms

A searching algorithm is used to find an item in a list or dataset. The two searching algorithms you must know for Edexcel 1CP2 are linear search and binary search.

Linear Search

A linear search (also called a sequential search) works by checking each element of the list one by one from the start until the target item is found or the list is exhausted.

Steps of a linear search

Start at the first element
Compare the current element with the target
If it matches — return its position
If not — move to the next element
If the end of the list is reached — the item is not present

Example: Search for 7 in the list [3, 9, 2, 7, 5, 1]: check 3 (no), 9 (no), 2 (no), 7 (yes! found at index 3).

Best case: The item is the first element — only 1 comparison needed.

Worst case: The item is last or not present — n comparisons (where n is the list size).

Linear search works on unsorted and sorted lists.

Binary Search

A binary search works by repeatedly halving the search space. It requires the list to be sorted in ascending order first.

Steps of a binary search

Find the midpoint of the list
Compare the midpoint value with the target
If it matches — return the position
If the target is less — discard the right half, repeat on the left half
If the target is greater — discard the left half, repeat on the right half
If the list is reduced to nothing — the item is not present

Example: Search for 7 in [1, 2, 3, 5, 7, 9, 11]:
Midpoint = 5 (index 3). Is 7 > 5? Yes → search right half [7, 9, 11].
Midpoint = 9. Is 7 < 9? Yes → search left half [7].
Midpoint = 7. Match! Found.

Best case: The target is the midpoint — 1 comparison.

Worst case: Logarithmic — about log₂(n) comparisons.

Comparing the Two Algorithms

Feature	Linear Search	Binary Search
Works on unsorted lists?	✓ Yes	✗ No — must be sorted
Speed on small lists	Acceptable	Fast
Speed on large lists	Slow (checks every item)	Very fast (halves each time)
Complexity	Linear — proportional to n	Logarithmic — proportional to log₂n
Simplicity	Simpler to implement	More complex

Exam tip: The most common exam question is to trace through one of these algorithms step by step on a given list, or to explain why binary search cannot be used on an unsorted list. Always state whether the list needs to be sorted.

⚠️ Common Mistakes

Saying binary search is always faster — it is NOT faster on very small lists and CANNOT be used on unsorted data without sorting first
Calculating the midpoint incorrectly — use (low + high) ÷ 2, rounding down
Forgetting that binary search discards half the list at each step — this is its key advantage
Confusing linear search with linear time complexity — linear search has linear time, binary search has logarithmic time

▶

Video coming soon

This lesson video is in production

Key points covered

How linear search works step by step with an example
How binary search halves the search space each time
Why binary search needs a sorted list
Comparing efficiency: linear vs binary search
Exam trace questions for both algorithms

Click slide or press arrow keys to navigate

✍️

Worksheet — 1.2b Searching Algorithms

8 Edexcel-style questions · instantly marked

Q1State one condition that must be met before a binary search can be used.[1 mark]

✅ Mark scheme

The list must be sorted (in ascending/descending order). [1 mark]

Q2Describe how a linear search works.[2 marks]

✅ Mark scheme

Each element in the list is checked one by one from the start [1]; if it matches the target, the position is returned; if the end is reached without finding it, the item is not in the list [1].

Q3Using binary search on the sorted list [2, 5, 8, 12, 16, 23, 38, 56], show all the steps needed to find the value 23.[3 marks]

✅ Mark scheme

Midpoint of 8 items = index 3 or 4 → value 12 or 16 [1]. 23 > midpoint → search right half [1]. New midpoint is 23 → match found [1]. (Accept any valid binary search trace on this list.)

Q4Give one advantage of binary search over linear search.[1 mark]

✅ Mark scheme

Binary search is faster/more efficient on large sorted lists because it halves the search space each time. [1 mark]

Q5Give one advantage of linear search over binary search.[1 mark]

✅ Mark scheme

Linear search works on unsorted lists / does not require the list to be sorted first. [1 mark]

Q6A database holds 1,000,000 sorted customer records. A manager wants to find one customer by ID. Explain which search algorithm should be used and why.[3 marks]

✅ Mark scheme

Binary search should be used [1] because the list is sorted [1]; it reduces the number of comparisons dramatically by halving the search space each time — for 1,000,000 records it takes at most about 20 comparisons rather than up to 1,000,000 [1].

Q7Explain what happens in the worst case when a linear search is performed on a list of n items.[2 marks]

✅ Mark scheme

The target item is either at the very end of the list [1] or not in the list at all, requiring n comparisons (every element must be checked) [1].

Q8A student wants to use binary search on the unsorted list [7, 2, 15, 4, 9]. The student sorts the list first to get [2, 4, 7, 9, 15]. Evaluate whether this approach is sensible.[3 marks]

✅ Mark scheme

The student is correct that sorting is needed before binary search [1]; however, for a list of only 5 items, the time to sort the list plus binary search is likely more than just doing a linear search directly [1]; the approach would only be sensible if many searches were to be performed on the same list, making sorting worthwhile [1].

Topic Quiz

Question 1 of 15

You scored

out of 15

Card 1 of 8

Click to reveal definition

🎉

Session complete!

Term	Definition

🔒

Unlock Pro

Subscribe to access all 59 Edexcel 1CP2 lessons.

£7.99/month

or £59/year

Searching Algorithms

Linear Search

Steps of a linear search

Binary Search

Steps of a binary search

Comparing the Two Algorithms

Key points covered

Worksheet — 1.2b Searching Algorithms

Mini Test — 1.2b Searching Algorithms

Unlock Pro