How do linear and binary search work, how do graph traversals explore data, and how efficient is each?
Searching and traversal algorithms: linear search and binary search with their conditions and efficiency, and the breadth-first and depth-first traversals of trees and graphs.
An Eduqas Component 1 answer on searching: how linear search and binary search work, the precondition that binary search needs sorted data, their time complexities, and how breadth-first and depth-first traversals explore trees and graphs.
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
Eduqas wants you to describe linear search and binary search, state binary search's precondition and each algorithm's efficiency, and describe how breadth-first and depth-first traversals explore trees and graphs. Search is one of the most heavily examined algorithm topics, usually with a trace and a complexity statement.
The answer
Linear search
Binary search
Breadth-first and depth-first traversal
Examples in context
A phone's contact search uses binary search because the contacts are kept sorted by name. A spell-checker scanning an unsorted buffer uses linear search. Breadth-first traversal powers shortest-route features in unweighted maps and "degrees of separation" in social graphs; depth-first traversal explores file-system trees, solves mazes and underlies cycle detection. The efficiency comparisons here lead directly into the next dot points on sorting and on Big-O notation, where the same complexity vocabulary is formalised.
Try this
Q1. State the precondition for binary search and its time complexity. [2 marks]
- Cue. The list must be sorted; complexity is .
Q2. A breadth-first traversal uses which auxiliary data structure? [1 mark]
- Cue. A queue.
Q3. Give one situation where linear search is more appropriate than binary search. [1 mark]
- Cue. When the list is unsorted (or very small), so sorting it first to enable binary search would not be worthwhile.
Exam-style practice questions
Practice questions written in the style of WJEC Eduqas exam questions on this dot point, with worked answer explainers. The year tag is the paper they imitate, not the source.
Eduqas 20205 marksA sorted array contains . Using a binary search, show the steps taken to find the value , stating the index examined at each step, and give the time complexity of binary search.Show worked answer →
Binary search on indices to (up to 3 marks). Step 1: middle index , value ; , so search the upper half, indices to . Step 2: middle , value ; found at index .
Time complexity (up to 2 marks): binary search halves the search space each step, so it is .
Markers reward the repeated halving with correct middle indices, the comparison that discards half the array each time, and the complexity. A common error is searching the wrong half after the comparison.
Eduqas 20224 marksCompare a breadth-first traversal with a depth-first traversal of a graph, stating the auxiliary data structure each uses and one situation where breadth-first is preferable.Show worked answer →
Breadth-first explores all neighbours of the current node before moving outward level by level, using a queue to hold the nodes to visit next (up to 2 marks).
Depth-first follows one branch as deep as possible before backtracking, using a stack (or recursion, which uses the call stack) (up to 1 mark).
Breadth-first is preferable when you need the shortest path in an unweighted graph, because it reaches nearer nodes first (up to 1 mark).
Markers reward the queue for breadth-first, the stack for depth-first, and the shortest-path use of breadth-first.
Related dot points
- Sorting algorithms: bubble sort and insertion sort and their quadratic efficiency, merge sort and quick sort and their use of divide and conquer, and comparing sorting algorithms by time complexity and stability.
An Eduqas Component 1 answer on sorting: how bubble and insertion sort work and why they are quadratic, how merge sort and quick sort use divide and conquer to reach n log n, and comparing the algorithms by time complexity.
- Recursion and algorithmic complexity: the base case and recursive case, how recursion uses the call stack, and Big-O notation for the time and space complexity of algorithms (constant, logarithmic, linear, polynomial and exponential).
An Eduqas Component 1 answer on recursion and complexity: the base case and recursive case, how recursion uses the call stack and can cause stack overflow, and Big-O notation for measuring how an algorithm's time and space scale with input size.
- Trees, graphs and hash tables: binary search trees and their traversals (in-order, pre-order, post-order), graphs as adjacency matrices and adjacency lists, and hashing for direct-access tables including collision handling.
An Eduqas Component 1 answer on trees, graphs and hash tables: binary search trees and in-order, pre-order and post-order traversals, representing graphs with an adjacency matrix or adjacency list, and hashing for fast direct access with collision handling.
- Dynamic data structures: stacks (LIFO) and queues (FIFO) with their push, pop, enqueue and dequeue operations and pointer management, linear and circular queues, and singly and doubly linked lists with insertion and deletion.
An Eduqas Component 1 answer on stacks, queues and linked lists: LIFO and FIFO behaviour, push, pop, enqueue and dequeue with pointer management, the wrap-around in a circular queue, and inserting and deleting nodes in a linked list.
- Static data structures: one- and multi-dimensional arrays, records (structs), tuples and sets, how they are stored contiguously in memory, address calculation for array elements, and choosing the appropriate structure for a task.
An Eduqas Component 1 answer on static data structures: one- and multi-dimensional arrays, records, tuples and sets, how they are stored contiguously in memory, calculating the address of an array element, and choosing the right structure for a problem.