gcsecomputerscience.co.uk
Search Precision 0 / 35
Seeker Rank Linear Seeker

Topic 2.1.2: Searching Algorithms

Linear Search vs Binary Search. Tracing and Efficiency.

1 [2 Marks]
(a) What condition must a list meet for a Binary Search?
(b) Why does a Linear Search not need this?
✅ Mark Scheme

(a) List must be SORTED (ordered).

(b) Linear Search checks every item sequentially, so order doesn't matter.

Score:
2 [3 Marks]
Tick the correct search algorithm for each statement.
Statement Linear Binary
Checks every item one by one.
Calculates a midpoint to divide the list.
Significantly faster for large, sorted lists.
✅ Mark Scheme
  • Checks every item: Linear
  • Calculates midpoint: Binary
  • Faster for large lists: Binary
Score:
3 [3 Marks]
Ali
Bea
Dan
Fay
Leo
Mia
Sam
Zoe
(a) How many checks to find "Sam"?
(b) What happens when searching for "Ben"?
✅ Mark Scheme

(a) 7 checks.

(b) Checks every item (Ali to Zoe), finds no match, reports "Not Found".

Score:
4 [4 Marks]
02
15
29
311
415
519
622
725
830
Show steps to Binary Search for 19.
Step 1: Midpoint (0+8)/2 = 4 (Value 15). 15 < 19, discard left.
Formula: Mid = (Low + High) / 2 (Round down).
Step 2 Range: Indices 5 to 8. Calculate new Mid.

Step 2: New Range [5-8]. Midpoint?

Step 3: New Range? Midpoint?

✅ Mark Scheme

Step 2: Range [5-8]. Mid = (5+8)/2 = 6. Value 22.
22 > 19, Discard Right.

Step 3: Range [5-5]. Mid = (5+5)/2 = 5. Value 19.
Found!

Score:
5 [3 Marks]
Binary Search for value 2. Complete the trace table.
Remember: If Target < MidValue, High=Mid - 1. If Target> MidValue, Low = Mid + 1.
Stage Low High Mid Value
1 0 8 4 15
2
3
✅ Mark Scheme

Stage 2: Low: 0, High: 3, Mid: 1, Value: 5

Stage 3: Low: 0, High: 0, Mid: 0, Value: 2 (Found)

Score:
6 [2 Marks]
array = [10, 45, 2, 19, 88, 30]
Why will Binary Search FAIL to find 19?
✅ Mark Scheme

The list is NOT sorted. Binary Search works by discarding half the list based on order logic. Without order, it might discard the half containing the item.

Score:
7 [4 Marks]
Complete the Linear Search Pseudocode.
WHILE index < length(list) AND found==False
  IF list[index] == THEN
    found =
  ELSE
    index = + 1
  ENDIF
ENDWHILE
IF found == False THEN print("")
✅ Mark Scheme

1. target (or item)

2. True

3. index

4. "Not Found"

Score:
8 [5 Marks]
Write the steps for a Binary Search algorithm.
Keywords: Midpoint, Compare, Discard, Repeat.
✅ Mark Scheme
  • Find midpoint.
  • Compare midpoint to target.
  • If match, stop (Found).
  • If target < mid, discard right half.
  • If target > mid, discard left half.
  • Repeat until found or empty.
Score:
9 [4 Marks]
Compare efficiency for 1,000,000 sorted items.
✅ Mark Scheme

Linear: Worst case checks 1,000,000 items (Very Slow).

Binary: Worst case checks approx 20 items (Log2 n) (Extremely Fast).

Score:
10 [2 Marks]
When is Linear Search faster than Binary Search? (e.g. list of 10 items).
✅ Mark Scheme

If the target is at the start of the list (Best Case). Linear finds it in 1 check. Binary might take a few divisions.

Score: