AlgorithmsTopic Summary
Knowledge Organiser: Linear Search and Binary Search
This topic summary covers Knowledge Organiser: Linear Search and Binary Search within Linear Search for GCSE Computer Science. Revise Linear Search in Algorithms for GCSE Computer Science with 15 exam-style questions and 8 flashcards. This topic appears less often, but it can still be a useful differentiator on mixed-topic papers. It is section 8 of 8 in this topic. Use this topic summary to connect the idea to the wider topic before moving on to questions and flashcards.
Topic position
Section 8 of 8
Practice
15 questions
Recall
8 flashcards
Knowledge Organiser: Linear Search and Binary Search
Key Terms
- Linear search: Checks each item in a list from the start until the target is found or the list ends
- Binary search: Repeatedly halves a sorted list to locate the target item
- Midpoint: The middle element of the current search range in binary search
- Sorted data: Data arranged in ascending or descending order — required for binary search
Must-Know Facts
- Linear search: works on unsorted data; checks every element in the worst case
- Binary search: data MUST be sorted first; much faster for large lists
- Linear search worst case: n comparisons (checks every item)
- Binary search worst case: log₂(n) + 1 comparisons
- Linear search is simpler to implement; binary search is more efficient at scale
- Binary search steps: find midpoint → compare → discard half → repeat
Key Concepts
- Linear: start at index 0, check each item, stop if found or list exhausted
- Binary: find midpoint → if target < mid, search left half; if target > mid, search right half
- Use linear when: data is unsorted, or list is very small
- Use binary when: data is already sorted and the list is large
- Binary is NOT always better — sorting takes time, so for a single search on unsorted data, linear may be faster overall
Common Mistakes
- Using binary search on unsorted data: Binary search only works on sorted lists — applying it to unsorted data will give incorrect results
- Saying binary search is always faster: For very small lists or unsorted data, linear search is simpler and may be faster overall (sorting first takes extra time)
- Getting the midpoint calculation wrong: The midpoint is calculated as the middle of the current search range, not the whole list — it changes each time a half is discarded
- Saying linear search is "inefficient" without context: Linear search is perfectly efficient for small or unsorted lists — efficiency depends on the context, not just the algorithm name
- Forgetting to show discarded halves in binary search traces: Exam answers must show which half is discarded each step — just stating "found" or "not found" loses method marks
Revise this topic interactively on PrepWise — self-test mode, tap-to-reveal definitions, and Common Mistakes from examiners.
Try the interactive Knowledge Organiser — free →