CS3: Searching Algorithms
How linear search and binary search work, with step-by-step examples and comparison of when to use each.
📋 What is a Searching Algorithm?
Definition: A searching algorithm finds the position of a specific item (the target) within a data structure such as a list or array. If the item is found, the algorithm returns its position; if not, it indicates the item is not present.
At GCSE, you need to know two searching algorithms:
- Linear search - checks each item one by one from the start
- Binary search - repeatedly halves the search space (requires sorted data)
🔍 Linear Search
Linear search checks each item in the list sequentially, starting from the first element, until the target is found or the end of the list is reached. It works on both sorted and unsorted data.
Algorithm in Pseudo-code
Linear Search Pseudo-code
FUNCTION linearSearch(list, target)
FOR i ← 0 TO LENGTH(list) - 1
IF list[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1
ENDFUNCTION
Step-by-Step Worked Example
Finding 7 in the list [3, 1, 7, 5, 9, 2]
Target: 7
| Step | Index | Value | Match? |
|---|---|---|---|
| 1 | 0 | 3 | No → move on |
| 2 | 1 | 1 | No → move on |
| 3 | 2 | 7 | Yes! → Return 2 |
Result: 7 found at index 2 after 3 comparisons.
Linear Search Performance:
Best case: 1 comparison (item is first)
Worst case: n comparisons (item is last or not present)
Average case: n/2 comparisons
Time complexity: O(n) - linear
Best case: 1 comparison (item is first)
Worst case: n comparisons (item is last or not present)
Average case: n/2 comparisons
Time complexity: O(n) - linear
🔲 Binary Search
Binary search works on a sorted list. It compares the target with the middle element. If the target is smaller, the search continues in the left half. If larger, it continues in the right half. This process repeats until the item is found or the search space is empty.
Algorithm in Pseudo-code
Binary Search Pseudo-code
FUNCTION binarySearch(list, target)
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high
mid ← (low + high) DIV 2
IF list[mid] = target THEN
RETURN mid
ELSEIF list[mid] < target THEN
low ← mid + 1
ELSE
high ← mid - 1
ENDIF
ENDWHILE
RETURN -1
ENDFUNCTION
Step-by-Step Worked Example
Finding 23 in the sorted list [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23 Low: 0 High: 9
| Step | Low | High | Mid | list[Mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 16 < 23 → search right half → low = 5 |
| 2 | 5 | 9 | 7 | 56 | 56 > 23 → search left half → high = 6 |
| 3 | 5 | 6 | 5 | 23 | 23 = 23 → Found! Return 5 |
Result: 23 found at index 5 after only 3 comparisons!
Finding 50 in the same list (not present)
| Step | Low | High | Mid | list[Mid] | Action |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 16 < 50 → low = 5 |
| 2 | 5 | 9 | 7 | 56 | 56 > 50 → high = 6 |
| 3 | 5 | 6 | 5 | 23 | 23 < 50 → low = 6 |
| 4 | 6 | 6 | 6 | 38 | 38 < 50 → low = 7 |
| 5 | 7 | 6 | - | - | low > high → not found. Return -1 |
Result: 50 is not in the list. Only 4 comparisons needed to confirm this.
Binary Search Performance:
Best case: 1 comparison (item is in the middle)
Worst case: log₂(n) comparisons (rounded up)
Time complexity: O(log n) - logarithmic
IMPORTANT: The list MUST be sorted first!
Best case: 1 comparison (item is in the middle)
Worst case: log₂(n) comparisons (rounded up)
Time complexity: O(log n) - logarithmic
IMPORTANT: The list MUST be sorted first!
⚖️ Comparing Linear and Binary Search
| Feature | Linear Search | Binary Search |
|---|---|---|
| Data requirement | Works on any list (sorted or unsorted) | Requires a sorted list |
| Time complexity | O(n) | O(log n) |
| Best case | 1 comparison | 1 comparison |
| Worst case (n=1000) | 1000 comparisons | 10 comparisons |
| Worst case (n=1,000,000) | 1,000,000 comparisons | 20 comparisons |
| Implementation | Simple - just loop through | More complex - needs low/high pointers |
| Adding items | Easy - just append | Must insert in correct position to maintain sort |
🤔 When to Use Each Algorithm
Use linear search when: the list is small, the list is unsorted, or you only need to search once.
Use binary search when: the list is large and already sorted, or you need to search the same list many times.
Decision Example
Scenario A: You have an unsorted list of 20 names and need to find one person.
→ Use linear search - the list is unsorted and small.
Scenario B: You have a sorted dictionary of 100,000 words and need to look up many words.
→ Use binary search - the list is large and sorted, and you're searching repeatedly.
⚠️ Common Mistakes
| Mistake | Why It's Wrong | How to Fix It |
|---|---|---|
| Using binary search on unsorted data | Binary search relies on the order to eliminate half the list | Sort the list first, or use linear search instead |
| Forgetting to update low/high correctly | Setting low=mid instead of mid+1 can cause infinite loops | Use low ← mid + 1 and high ← mid - 1 |
| Using integer division incorrectly for mid | Floating-point mid values cause errors | Use mid ← (low + high) DIV 2 |
| Stopping too early in binary search | The item might be in the remaining half | Continue until low > high |
❓ Practice Questions
Q1: Describe how a linear search works.
Q2: Why must data be sorted before binary search can be used?
Q3: Perform a binary search for the value 72 in the list [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]. Show each step.
Q4: A sorted list contains 256 items. What is the maximum number of comparisons needed by binary search?
Q5: Explain one advantage and one disadvantage of linear search compared to binary search.
✅ Answers
- A linear search checks each item in a list one by one, starting from the first element, until the target is found or the end of the list is reached. It works on both sorted and unsorted data.
- Binary search compares the target with the middle element and eliminates half the list based on whether the target is smaller or larger. This only works if the list is sorted, because the algorithm relies on the fact that all items before the middle are smaller and all items after are larger.
- Step 1: low=0, high=9, mid=4, list[4]=16. 16<72, so low=5. Step 2: low=5, high=9, mid=7, list[7]=56. 56<72, so low=8. Step 3: low=8, high=9, mid=8, list[8]=72. 72=72, found at index 8.
- log₂(256) = 8. Maximum 8 comparisons.
- Advantage: Linear search works on unsorted data, unlike binary search. Disadvantage: Linear search is much slower for large datasets - O(n) vs O(log n).
🎯 Exam Tips
- Always state that binary search requires sorted data
- In binary search, use mid ← (low + high) DIV 2 (integer division)
- Show your working in step-by-step questions - draw a table with low, high, mid columns
- When comparing, mention time complexity: O(n) vs O(log n)
- Don't forget: linear search can work on unsorted data, binary search cannot
- Practise working through binary search step-by-step on paper - this is a common exam question
⚠️ Common Errors
✗ Thinking binary search works on unsorted data ✓ Binary search requires the data to be sorted first; it halves the search space by comparing to the middle element, which only works on ordered data.
✗ Confusing linear search and binary search time complexities ✓ Linear search is O(n) — checks each item in turn. Binary search is O(log n) — halves the search space each step. Binary search is faster for large sorted datasets.
✗ Believing binary search is always better than linear search ✓ Binary search only works on sorted data and has more complex logic; for small or unsorted datasets, linear search may be simpler and equally effective.
✗ Forgetting that linear search works on any data order ✓ Linear search checks each item sequentially and works on both sorted and unsorted data — it does not require the data to be in any particular order.
✍️ Model Answer
Full-Mark Response
A sorted list contains 1024 student names. Compare the maximum number of comparisons needed by linear search and binary search to find a specific name. [4 marks]
Linear search: In the worst case, it would check all 1024 items, so the maximum number of comparisons is 1024 (O(n)). Binary search: Each comparison halves the search space: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. This takes a maximum of 10 comparisons (O(log₂ n), since 2¹⁰ = 1024). Binary search is significantly more efficient for this sorted dataset, requiring at most 10 comparisons compared to 1024 for linear search.
📊 AO Deep Dive
Assessment Objective Analysis
AO1 (Computational Thinking — 40%): Demonstrate knowledge and understanding of the principles and concepts of computer science, including searching algorithms: linear and binary search for AQA 8525, OCR J277 & Edexcel 1CP2.
AO2 (Application — 40%): Apply knowledge and understanding of computer science, including searching algorithms: linear and binary search to analyse problems in computational terms and to design, write and evaluate solutions.
AO3 (Evaluation — 20%): Evaluate the effectiveness, correctness and efficiency of computational solutions, including searching algorithms: linear and binary search, and make reasoned judgements about trade-offs.
📝 Exam Technique
GCSE Computer Science Exam Tips:
When comparing search algorithms, always state the time complexity of each (O(n) vs O(log n)) and explain what this means in practice. For binary search, always mention that the data MUST be sorted. Show your working for maximum comparisons: for binary search, calculate log₂(n). For linear search, the worst case is n comparisons. Use a worked example with a specific value of n to illustrate.
When comparing search algorithms, always state the time complexity of each (O(n) vs O(log n)) and explain what this means in practice. For binary search, always mention that the data MUST be sorted. Show your working for maximum comparisons: for binary search, calculate log₂(n). For linear search, the worst case is n comparisons. Use a worked example with a specific value of n to illustrate.
📝 Exam Questions by Topic
🎬 Video Resources
Ready to ace your GCSE Computer Science exams?
Get the best revision books and guides to boost your grades.