The big idea: Linear search checks each item in turn until it finds the target or runs out.
Binary search starts in the middle and throws away half the list at every step — but it only works on a sorted list.
Both searching the same sorted list for the same target. Watch the comparison counts diverge.
Interactive diagram
Explore the labelled diagram, charts and maps for this topic in full study mode.
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
What it gives you
- Works on any list, sorted or not
- Simple, and hard to get wrong
- Best case O(1) — the target is first
- Finds the first match when there are several
What it costs
- Worst case O(n) — the target is last, or absent
- Average about n/2 comparisons
- On a million items, up to a million comparisons
When to use it
- The list is unsorted and will stay that way
- The list is small, so the difference does not matter
- You search it rarely, so sorting first would not pay
Returning -1 for not found: Every position is a valid answer, including 0 — so "not found" needs a value that is not a position.
-1 is the convention, and the caller must check for it before using the result.
Stop wasting time on topics you know
Our AI identifies your weak areas and focuses your study time where it matters. No more overstudying easy topics.
The three cases
Why mid + 1 and mid - 1
When it stops
The cost
It requires sorted data: Discarding half depends on knowing which half the target would be in — which only holds if the list is in order.
On unsorted data, binary search does not run slowly; it returns the wrong answer.
How this is tested — you must trace the comparisons and justify the choice from sortedness and size. It comes up two ways:
Paper 2 — working with code
- Trace a search and count the comparisons, 4-6 marks
- Choose between the two for a scenario
- Explain why binary search needs sorted data
Paper 2 — the algorithmic-thinking question
- Reason about comparison counts with no code shown
- Explain how the search terminates
The classic trap: Choosing binary search because it is faster, without checking the data is sorted. On unsorted data it does not run slowly — it silently gives the wrong answer.
Trace a binary search for 23 in [3, 7, 11, 14, 19, 23, 28, 31], stating each comparison, and say how many a linear search would need.
Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.