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.
Check the order first: A binary search gives wrong answers on a list that is not sorted.
To check while values are read in, keep the previous value and compare each new one with it: if a value is smaller than the one before, the list is not in ascending order.
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.
def linear_search(items, target):
for i in range(len(items)):
if items[i] == target:
return i # found — the position
return -1 # ran out — not presentstatic int linearSearch(int[] items, int target) {
for (int i = 0; i < items.length; i++) {
if (items[i] == target) {
return i; // found — the position
}
}
return -1; // ran out — not present
}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.
def binary_search(items, target):
low = 0
high = len(items) - 1
while low <= high:
mid = (low + high) // 2
if items[mid] == target:
return mid
elif items[mid] < target:
low = mid + 1 # discard the left half
else:
high = mid - 1 # discard the right half
return -1static int binarySearch(int[] items, int target) {
int low = 0;
int high = items.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (items[mid] == target) {
return mid;
} else if (items[mid] < target) {
low = mid + 1; // discard the left half
} else {
high = mid - 1; // discard the right half
}
}
return -1;
}The three cases
Look at the middle. Equal — done. Too small — the target must be to the right, so move low past it. Too big — move high before it.
Each case removes about half of what remains.
Why mid + 1 and mid - 1
The middle has just been checked and is not the target, so it must be excluded from the next range.
Using mid instead of mid + 1 leaves it in, and the loop never ends.
When it stops
low passes high, meaning nothing is left to search — so the target is absent and it returns -1.
That is the condition to state when a question asks how it terminates.
The cost
O(log n). Sixteen items need at most four comparisons; a million need about twenty.
Doubling the list adds exactly one comparison.
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 answer broken into clear points, with guidance on how each point earns marks.