CAIE 9618 · Paper 4 · Topic 4.4.2

Searching &
Graph Algorithms

Linear Search · Binary Search · BFS · DFS · Dijkstra's Shortest Path

CSZone Cambridge International AS & A Level Computer Science 9618

Linear Search vs Binary Search

Searching an Array

Linear Search

Check each element one by one from the start

Works on unsorted AND sorted data

O(n) — must check up to n elements

O(1) space; simple to implement

Best case: O(1) — target is first element
Average/worst case: O(n)

Binary Search

Requires sorted data

Compare target with middle element; discard half the list each step

O(log n) — much faster for large n

Find 7 in [1,3,5,7,9,11,13]:
Mid=7 → found! 1 comparison

Find 5 in [1,3,5,7,9,11,13]:
Mid=7 (idx 3). 5 < 7 → search left half
Mid=3 (idx 1). 5 > 3 → search right half
Mid=5 (idx 2). Found! 3 comparisons (log₂7≈3)

Max comparisons: ⌈log₂(n+1)⌉

BFS & DFS Graph Traversal

Exploring Graphs & Trees

BFS — Breadth-First Search

Explores all neighbours at current depth before going deeper

Uses a QUEUE — visit node, enqueue all unvisited neighbours

Finds shortest path in unweighted graphs

Level-by-level traversal

Use: shortest path, web crawlers, social network degrees of separation, network broadcasting

DFS — Depth-First Search

Explores as far as possible along each branch before backtracking

Uses a STACK (or recursion call stack)

Uses less memory than BFS in wide graphs

Does NOT guarantee shortest path

Use: maze solving, topological sort, cycle detection, tree traversals (pre/in/post-order)

DIJKSTRA'S SHORTEST PATH

Finds shortest path in a weighted graph. Greedy algorithm — always relaxes the edge to the nearest unvisited node. Uses a priority queue. O((V+E) log V) with a min-heap. Cannot handle negative edge weights.

Exam Practice

Cambridge-style questions

Question 1

A sorted array contains [2, 5, 8, 12, 16, 23, 38, 56]. Trace a binary search for the value 23, stating the mid index and whether the search continues left or right at each step. State the number of comparisons made. [3]

1

Low=0, High=7. Mid=(0+7)DIV2=3. Array[3]=12. 23 > 12 → search right half. Low=4.

1

Low=4, High=7. Mid=(4+7)DIV2=5. Array[5]=23. 23 = 23 → Found!

1

Total comparisons: 2. (Binary search: max comparisons = ⌈log₂ 8⌉ = 3)

Common Mistakes

Don't lose easy marks

1

Applying binary search to an unsorted list — binary search ONLY works on sorted data. If the data is unsorted, you MUST use linear search (or sort first, then binary search, which may not be worth it for a single search).

2

Saying BFS uses a stack — BFS uses a QUEUE (FIFO) to process nodes level by level. DFS uses a STACK (LIFO) to go deep first. The wrong data structure completely changes the traversal order.

3

Calculating the mid index wrongly — use Mid = (Low + High) DIV 2 (integer division). In CAIE pseudocode use DIV for integer division. Off-by-one errors in index calculation cause incorrect trace table outputs.

Topic Summary — 4.4.2

What You Need to Know

SEARCHING

Linear: O(n), works on any data. Binary: O(log n), requires sorted data, Mid=(Low+High) DIV 2, search left/right of mid. Binary vastly faster for large n.

GRAPH TRAVERSAL

BFS: queue, level-by-level, shortest path in unweighted graphs. DFS: stack/recursion, depth-first, cycle detection, maze solving. Both O(V+E).

DIJKSTRA

Shortest path in weighted graphs. Greedy — always visits nearest unvisited node. Priority queue. No negative weights. O((V+E) log V).

CSZone

Next Video

4.4.3

Algorithm Complexity

Big-O Notation · Time vs Space · O(1) to O(n!)

Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools