Comparing searching algorithms
Lesson details
Learning outcome
I can compare and contrast linear and binary search and trace the code for both searching algorithms.
Key learning points
- The searching algorithm you use will depend on the data and context you are using.
- Coding a binary search is more complex than a linear search.
- Tracing code for searching algorithms by completing a trace table can help you check how efficient the algorithm is.
Keywords
Algorithm - a set of step-by-step instructions to solve a problem
Trace table - a tool used to track the values of variables and the flow of execution in an algorithm or program, step by step
Common misconception
A linear search algorithm and binary search algorithm are equally complex to write.
Binary search algorithms are more complex to write due to the different paths that the algorithm can take rather than stepping through the search data in order.
Teacher tip
Pupils might benefit from coding the algorithms themseleves based on the steps modelled. Simply reading the code is often not enough to understand the principle of its operation.
Licence
Lesson video
Loading...
Prior knowledge starter quiz
6 Questions
Q1.What is the name of the algorithm that checks each item in a list one by one until the desired item is found?
Q2.Which of these is true about linear search?
Q3.What does binary search do with the data set at each step?
Q4.What must be true about a list for binary search to work?
Q5.Which of these is an example of a sorted list?
Q6.How many comparisons does binary search make in the best-case scenario?
Assessment exit quiz
6 Questions
Q1.Arrange the steps of a linear search in the correct order:
Q2.Arrange the steps of binary search:
Q3.Match the situation to the concept:
linear search
binary search
trace table
algorithm
Q4.What is a trace table used for?
Q5.Which searching algorithm is more complex to write?
Q6.Which of these is true about linear search?
To help you plan your 10 computer science lesson on: Comparing searching algorithms, download all teaching resources for free and adapt to suit your pupils' needs...
To help you plan your 10 computer science lesson on: Comparing searching algorithms, download all teaching resources for free and adapt to suit your pupils' needs.
The starter quiz will activate and check your pupils' prior knowledge, with versions available both with and without answers in PDF format.
We use learning cycles to break down learning into key concepts or ideas linked to the learning outcome. Each learning cycle features explanations with checks for understanding and practice tasks with feedback. All of this is found in our slide decks, ready for you to download and edit. The practice tasks are also available as printable worksheets and some lessons have additional materials with extra material you might need for teaching the lesson.
The assessment exit quiz will test your pupils' understanding of the key learning points.
Our video is a tool for planning, showing how other teachers might teach the lesson, offering helpful tips, modelled explanations and inspiration for your own delivery in the classroom. Plus, you can set it as homework or revision for pupils and keep their learning on track by sharing an online pupil version of this lesson.
Explore more key stage 4 computer science lessons from the Searching and sorting algorithms unit, dive into the full secondary computer science curriculum, or learn more about lesson planning.