📘 Paper 2 · Topic 7: Algorithm Design & Problem Solving
7.3a Linear & Binary Search
Cambridge IGCSE Computer Science 0478 · ~15 min read · ⭐ Pro

Linear Search

A linear search (sequential search) checks each item in a list one by one from the beginning until the target is found or the end is reached.

How it works

  • Start at the first element (index 0 or 1)
  • Compare the current element to the target
  • If it matches — found!
  • If not — move to the next element
  • If you reach the end — the item is not in the list

Pseudocode — Linear Search

found ← FALSE
index ← 1
WHILE index <= length AND found = FALSE DO
    IF list[index] = target THEN
        found ← TRUE
    ELSE
        index ← index + 1
    ENDIF
ENDWHILE
IF found = TRUE THEN
    OUTPUT "Found at position ", index
ELSE
    OUTPUT "Not found"
ENDIF

Example — searching for 42 in: 7, 15, 42, 3, 91

7 15 42 3 91

Checks: 7 (no) → 15 (no) → 42 ✓ Found at position 3

Advantages and disadvantages of linear search

AdvantagesDisadvantages
Works on unsorted dataSlow for large lists (checks every element)
Simple to implement and understandMaximum comparisons = number of items (n)
Can be used on any data typeNot efficient

Binary Search

A binary search is a much more efficient algorithm — but it requires the data to be sorted in order first. It works by repeatedly halving the search space.

How it works

  • Find the middle item of the sorted list
  • If the middle item equals the target — found!
  • If the target is less than the middle — search the left half
  • If the target is greater than the middle — search the right half
  • Repeat until found or the search space is empty

Pseudocode — Binary Search

low ← 1
high ← length
found ← FALSE
WHILE low <= high AND found = FALSE DO
    mid ← (low + high) DIV 2
    IF list[mid] = target THEN
        found ← TRUE
    ELSE IF list[mid] < target THEN
        low ← mid + 1
    ELSE
        high ← mid - 1
    ENDIF
ENDWHILE
IF found = TRUE THEN
    OUTPUT "Found at position ", mid
ELSE
    OUTPUT "Not found"
ENDIF

Example — searching for 42 in sorted list: 3, 7, 15, 42, 91

Step 1: low=1, high=5, mid=3
37154291
Middle is 15. Target (42) > 15 → search right half
Step 2: low=4, high=5, mid=4
37154291
✓ Found at position 4 — only 2 comparisons!

Comparison: Linear vs Binary Search

Linear SearchBinary Search
Data must be sorted?NoYes
Maximum comparisons (n=1000)1000~10 (log₂ 1000)
EfficiencyLow (for large data)High
ComplexitySimpleMore complex
Works on linked lists?YesDifficult
Exam tip: For binary search on n=16 items, the maximum comparisons = log₂(16) = 4. You do not need to know Big-O notation for IGCSE, but you should know that binary search is "more efficient" than linear search for large datasets, and state WHY (it halves the search space each time).
⚠️ Common Mistakes
  • Saying binary search can work on unsorted data — it CANNOT. It only works correctly on sorted data.
  • Not using DIV for the midpoint (must be integer division)
  • Updating low/high incorrectly: low ← mid+1 (not mid) and high ← mid-1 (not mid)
▶
Video coming soon
Click slide or press arrow keys to navigate
✍️

Worksheet — Search Algorithms

5 questions · 10 marks

Q1State one advantage and one disadvantage of a linear search compared to binary search. [2]
✅ Mark scheme
Advantage: works on unsorted data [1]; Disadvantage: slower/less efficient for large datasets — must check every element in the worst case [1]
Q2A binary search is performed on the list: 2, 8, 14, 21, 35, 47, 60, 73. Show how the algorithm finds the value 35. State the mid value at each step. [3]
✅ Mark scheme
Step 1: low=1, high=8, mid=4 → list[4]=21, 35>21 so low=5 [1]; Step 2: low=5, high=8, mid=6 → list[6]=47, 35<47 so high=5 [1]; Step 3: low=5, high=5, mid=5 → list[5]=35 ✓ Found [1]
Q3Explain why binary search cannot be used on an unsorted list. [2]
✅ Mark scheme
Binary search works by comparing the target to the middle element and then deciding to search the left or right half [1]. This logic assumes the data is sorted — if it is not, smaller/larger values may be on the wrong side and the algorithm will incorrectly eliminate the correct half [1]
Q4For a list of 32 items, what is the maximum number of comparisons binary search would need? Show your working. [2]
✅ Mark scheme
Maximum comparisons = log₂(32) = 5 [1]; working: 32→16→8→4→2→1 (5 halvings) [1]
Q5In a binary search, if the target is less than the middle element, what happens to the search space? [1]
✅ Mark scheme
The search space is restricted to the left half — high is set to mid - 1 [1]
Quiz — Linear & Binary Search
Q 1 of 8
Score
/ 8
Click to reveal
TermDefinition
🎯

Mini Test — Searching

10 minutes · mixed marks

← 7.2b Trace Tables Topic 7: Algorithm Design Next: 7.3b Bubble Sort →
🔒
Pro Content
Upgrade to access all lessons.
£7.99/month
or £59/year
Subscribe now →