1. What condition does ordinary binary search require?
- Sorted data
- Random order
- Unique text values only
Check the answer and reasoning
Sorted data
Ordering lets the search safely discard one half after each comparison.
CS / AS level
Algorithms and data structures
Arrays, records, stacks and queues organise values for different operations. Linear search examines candidates in sequence; binary search repeatedly halves a sorted interval.
Learning objectives
- Explain algorithms and data structures using a concrete example.
- Apply the worked method and justify each step.
- Recognise the limitation described in the final check.
The big idea
Arrays, records, stacks and queues organise values for different operations. Linear search examines candidates in sequence; binary search repeatedly halves a sorted interval.
Trace invariants and termination conditions rather than memorising code. A stack is last-in-first-out, while a queue is first-in-first-out; neither rule alone determines a physical implementation.
Worked example
Push A, then B onto an empty stack; pop once. What is returned?
Follow the solution
The most recently pushed item is removed first.
Investigate and explain
Predict the worked result before calculating. Change one input, record the new result, and explain which assumptions still hold.
Use the prediction activity below; a local model appears only where it supports this topic.
Check your understanding
2. Push A, then B onto an empty stack; pop once. What is returned?
- A
- B
- Both together
Check the answer and reasoning
B
The most recently pushed item is removed first.
3. Does binary search examine every element on a successful typical search?
- Yes
- Only for integers
- No
Check the answer and reasoning
No
It narrows the candidate interval; linear scanning is a different algorithm.