What is not halving correctly?

After each comparison, keep only the half that could contain the target, then find the new middle of that half.

SingaporeComputer ScienceSyllabus dot point

How do linear and binary search find an item, and why is binary search faster?

Describe and trace linear search and binary search, and explain why binary search needs a sorted list

A focused answer to the O-Level Computing point on searching. How linear search checks each item in turn, how binary search halves a sorted list each step, and why binary search is faster but needs sorted data.

Generated by Claude Opus 4.87 min answerUpdated 2026-06-06

Reviewed by: AI editorial process; not yet individually human-reviewed

Have a quick question? Jump to the Q&A page

Jump to a section

What this dot point is asking
The answer
Examples in context
Try this

What this dot point is asking

SEAB wants you to describe and trace two search algorithms, linear search and binary search, and to explain why binary search needs a sorted list and is faster. The central idea is that linear search checks items one by one, while binary search repeatedly halves a sorted list, so it reaches the answer in far fewer steps.

The answer

Linear search

A linear search starts at the first item and checks each one in turn until it finds the target or runs out of items.

FOR each item in the list
    IF item = target THEN
        OUTPUT "found"
        STOP
    ENDIF
NEXT
OUTPUT "not found"

It works on any list, sorted or not. In the worst case (the item is last or missing), it checks every item, so for $n$ items it may need up to $n$ comparisons.

Binary search

A binary search works only on a sorted list. It checks the middle item, then discards the half that cannot contain the target:

Look at the middle item.
If it is the target, stop.
If the target is smaller, repeat on the left half.
If the target is larger, repeat on the right half.

Each step throws away half the remaining items, so the list shrinks quickly.

list: [3, 7, 11, 15, 19, 23, 27]   target 11
middle 15 -> 11 < 15, take left half [3, 7, 11]
middle 7  -> 11 > 7,  take right half [11]
middle 11 -> found

Why binary search needs a sorted list

Binary search depends on knowing that everything left of the middle is smaller and everything right is larger. That is only true if the list is sorted. On an unsorted list this assumption fails, so the algorithm could throw away the half that actually holds the target.

Why binary search is faster

Because each step halves the list, the number of comparisons grows very slowly. A list of $1000$ items needs at most about $10$ comparisons by binary search ( $2^{10} > 1000$ ), but up to $1000$ by linear search. The bigger the list, the greater the advantage.

Examples in context

Example 1. Finding a name in a phone book. A printed phone book is sorted, so you naturally use a binary-search style: open the middle, decide which half the name is in, and repeat. You never read every entry, which is why a sorted book is quick to search.

Example 2. Searching an unsorted inbox. Looking through unsorted emails for one from a particular sender, with no order to exploit, is a linear search: you check messages one by one until you find it. Sorting the inbox by sender first would let a binary-search approach work.

Try this

Q1. State one advantage of linear search over binary search. [2 marks]

Cue. It works on any list, sorted or not, with no need to sort the data first.

Q2. A sorted list has $16$ items. State the maximum number of comparisons a binary search needs. [2 marks]

Cue. $4$ , because $2^4 = 16$ , so the list halves at most four times.

Q3. Explain why binary search needs the list to be sorted. [2 marks]

Cue. It discards a half based on order; only a sorted list guarantees the target is not in the discarded half.

Exam-style practice questions

Practice questions written in the style of SEAB exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.

Original5 marksA sorted list holds

[3, 7, 11, 15, 19, 23, 27]

. Trace a binary search for the value

19

. State the middle value checked at each step and whether the search goes left or right, then give the number of comparisons.

Show worked answer →

Binary search checks the middle, then halves the list.

Step 1: list [3,7,11,15,19,23,27], middle = 15. 19 > 15, search the right half.
Step 2: right half [19,23,27], middle = 23. 19 < 23, search the left half.
Step 3: left half [19], middle = 19. Found.

The middle values checked were $15$ , $23$ , $19$ , so the value was found in $3$ comparisons.

Markers reward checking the middle each time, moving right then left correctly, finding $19$ , and the count of $3$ comparisons.

Original5 marks(a) Describe how a linear search works. (b) Explain why binary search cannot be used on an unsorted list. (c) For a list of

1000

items, state roughly the maximum number of comparisons each method needs.

Show worked answer →

(a) A linear search checks each item in turn from the start until it finds the target or reaches the end of the list. If it reaches the end without a match, the item is not present.

(b) Binary search works by comparing the target with the middle item and discarding the half that cannot contain it. This only works if the list is sorted, because the algorithm relies on knowing that everything to one side of the middle is smaller and everything to the other side is larger. On an unsorted list that assumption is false, so it could discard the half that actually contains the item.

(c) Linear search may need up to $1000$ comparisons (every item). Binary search needs at most about $10$ , because each step halves the list ( $2^{10} = 1024 > 1000$ ).

Markers reward checking items in turn for linear search, binary search needing sorted data to halve safely, and roughly $1000$ versus $10$ comparisons.