Linear Search · Binary Search · Comparing Efficiency
CSZoneEdexcel GCSE Computer Science 1CP2
Linear Search
Check Every Item in Order
Linear search checks each item in a list one by one from the start until the target is found or the end is reached. Works on unsorted and sorted lists.
Best case: target is first item — 1 comparison
Worst case: target is last or not in list — n comparisons
Simple to implement; suitable for small or unsorted lists
Inefficient for large datasets — must check every item
Binary Search
Divide and Conquer
Binary search requires the list to be sorted. It repeatedly halves the search space: check the middle item — if too high, discard the right half; if too low, discard the left half. Repeat until found.
Far fewer comparisons than linear search for large lists
Comparing the Two
Which Search is Better?
Linear search: works on any list; slow for large lists (O(n)); simple code
Binary search: needs sorted list; very fast for large lists (O(log n)); more complex code
When to use binary: large sorted datasets. When to use linear: small or unsorted data, or when sorting would cost more than searching.
Exam Practice
Have a go at this question
Edexcel-style question
Give two reasons why a binary search would be more efficient than a linear search on a list of 10,000 sorted names.
2 marks
Binary search halves the search space each step, so the maximum comparisons is log₂(10000) ≈ 14, compared to up to 10,000 for linear search [1]. Binary search is therefore much faster and requires far fewer comparisons to locate an item [1].
Key Takeaways
What to Remember
Linear search: checks each item; works on unsorted lists; slow for large n
Binary search: halves search space each time; requires sorted list; very fast
Binary: max comparisons = log₂(n); Linear: max comparisons = n