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: the list is halved every step, so far fewer checks than linear search
- 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