Linear vs binary search comparison

Compare linear search and binary search. Your answer should include: when each is appropriate, and their efficiency. [6 marks]

Mark scheme (levels-based):

L2 (3–4): Describes both algorithms; identifies key differences (sorted list requirement; efficiency).

L3 (5–6): Sustained comparison: linear requires no precondition → versatile; best for small or unsorted lists. Binary requires sorted list → sorting overhead if not already sorted; far more efficient for large sorted lists (log₂n vs n worst case). Example: searching 1 million items — binary max 20 comparisons, linear max 1 million. Binary search should be used when the list is large AND already sorted; linear when the list is small or unsorted.