How Each Works · Pseudocode · Comparison · When to Use Each
CSZoneCambridge IGCSE Computer Science 0478
Linear Search
Check Each Item in Turn
Linear search: starts at the first item and checks each one in order until the target is found or all items have been checked. Works on unsorted lists.
found ← FALSE i ← 1 WHILE i <= n AND found = FALSE DO IF data[i] = target THEN found ← TRUE ELSE i ← i + 1 ENDIF ENDWHILE IF found THEN OUTPUT i ELSE OUTPUT "Not found"
Binary Search
Halve the Search Space Each Time
Binary search: only works on a sorted list. Finds the middle item; if target is less, search the left half; if greater, search the right half. Repeat until found or list exhausted.
low ← 1 high ← n found ← FALSE WHILE low <= high AND found = FALSE DO mid ← (low + high) DIV 2 IF data[mid] = target THEN found ← TRUE ELSE IF target < data[mid] THEN high ← mid - 1 ELSE low ← mid + 1 ENDIF ENDWHILE
Comparison: Linear vs Binary
Which is Better and When?
Feature
Linear Search
Binary Search
List must be sorted?
No
Yes
Speed (worst case)
Slow (checks all n)
Fast (log₂ n checks)
Works for small lists?
Yes
Yes
Best for large lists?
No
Yes
Example: binary search on 1000 items needs at most ~10 checks; linear search needs up to 1000
Exam Practice
Have a go at this question
Cambridge IGCSE 0478 style
A sorted list contains [2, 5, 8, 12, 17, 23, 30]. Trace a binary search for the value 17, showing the value of low, high and mid at each step.