IB Computer Science HL · Year 2 · Lesson 7
Linear and binary search
Algorithms must be understood operationally: how they behave, how to trace them, and when their efficiency makes them suitable.
Paper 250 minutesB2.4.2
Use Next or the arrow keys.
Today’s targets
What you need to be able to do
2 / 8
- Construct + traceAnd trace algorithms to implement a linear search and a binary search for data retrieval
B2.4.2
Paper 2 lensMatch the depth of every response to the command term. Previously learned content can move quickly, but retrieval must still be accurate.
Page 2 of 8
Retrieve
Rapid Recall Deck
3 / 8
Say the answer aloud before flipping. Mark secure knowledge quickly and spend time on the gaps.
- How does a linear search find a target?: It checks elements one by one until it finds the target or reaches the end of the data.
- What prerequisite does binary search have?: The data must be ordered according to the value being searched.
- How does binary search reduce the search space?: It compares with the middle item and repeatedly discards the half that cannot contain the target.
- How do linear and binary search differ in scalability?: Linear search is O(n) in the worst case; binary search is O(log n) when its ordering requirement is satisfied.
- When might linear search be preferable to binary search?: When the data is unsorted, small, or the cost of sorting/indexing would outweigh the benefit of binary search.
Page 3 of 8
B2.4.2 · Learn
Core knowledge and application
4 / 8
B2.4.2Construct + trace
And trace algorithms to implement a linear search and a binary search for data retrieval
Algorithms must be understood operationally: how they behave, how to trace them, and when their efficiency makes them suitable.
Exam moveProduce the required code, diagram, query, model or representation accurately.
Required detail 1The differences in efficiency between different methods of linear and binary search
Required detail 2Use of search technique based on efficiency requirements—for example, searching a database for a sorted/indexed list of names to find a phone number, versus searching by the number to identify the name
Assessment boundaryPaper 2
Explain it without notes
Construct + trace: And trace algorithms to implement a linear search and a binary search for data retrieval in the context of a program that searches and organizes a growing dataset.
- The differences in efficiency between different methods of linear and binary search
- Use of search technique based on efficiency requirements—for example, searching a database for a sorted/indexed list of names to find a phone number, versus searching by the number to identify the name
Page 4 of 8
Trace / construct
Programming checkpoint
5 / 8
def binary_search(data, target):
low, high = 0, len(data) - 1
while low <= high:
mid = (low + high) // 2
if data[mid] == target: return mid
if data[mid] < target: low = mid + 1
else: high = mid - 1
return -1static int binarySearch(int[] data, int target) {
int low = 0, high = data.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (data[mid] == target) return mid;
if (data[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}Before you run itTrace the code by hand. Identify state changes, branch/loop behaviour, and the final result.
Modify it
Change one condition, input or operation so the program solves a slightly different problem. Predict the effect before editing.
Page 5 of 8
Apply
Transfer to a new scenario
6 / 8
ScenarioA program that searches and organizes a growing dataset needs a design or technical decision related to today’s topic. Explain what matters and why.
- The differences in efficiency between different methods of linear and binary search
- Use of search technique based on efficiency requirements—for example, searching a database for a sorted/indexed list of names to find a phone number, versus searching by the number to identify the name
Page 6 of 8
Exam lens
Paper 2 practice
7 / 8
Build the response before checking notesUse precise terminology and match the required depth.
- Construct + trace: And trace algorithms to implement a linear search and a binary search for data retrieval in the context of a program that searches and organizes a growing dataset.
Self-checkAnswer the exact command term. For explain, include mechanism/reason; for compare, pair criteria; for discuss/evaluate/justify, build supported reasoning and a conclusion.
Page 7 of 8
Homework
Finish the learning cycle
8 / 8
IA — main task
Refine Criteria A/B/C. Use today’s lesson to make the problem specification, decomposition, algorithms or testing plan more precise where relevant.
Syllabus — 10–15 min
Repeat the recall deck and complete the lesson response prompt without model support.
Designed by David Xu
© 2026 David Xu. All rights reserved.
Educators and students are welcome to use these materials for non-commercial teaching and learning with attribution. Please share the original link when possible. Reposting, redistributing modified copies, removing attribution, or commercial use requires prior permission.
End of Lesson 7.