Searching Sorting Algorithms

Overview

Year 13 Digital Technologies students prepare for the NZQA AS91908 external examination, focusing on the 2026 Complexity and tractability topic. Students compare searching and sorting algorithms, analyse how problem size affects efficiency, distinguish tractable from intractable problems, and practise communicating justified analysis at Achievement, Merit and Excellence depth.

Prior knowledge

Students should understand that a computer program is a precise sequence of instructions, and be familiar with variables, comparison operators and basic pseudocode. Briefly revisit these ideas if needed.

Learning intentions

Students will:

• compare linear and binary search, including the conditions required for each
• compare sorting approaches and explain how sorting can affect search efficiency
• explain how problem size affects algorithm efficiency and computational feasibility
• distinguish between tractable and intractable problems
• communicate justified analysis at Achievement, Merit and Excellence depth for NZQA AS91908

Success criteria

• I can compare linear and binary search and explain when each is appropriate.
• I can compare sorting approaches and explain how sorting may improve searching efficiency.
• I can explain how increasing problem size affects efficiency and feasibility.
• I can distinguish tractable problems from intractable problems using justified reasoning.
• I can communicate analysis with appropriate justification at Achievement, Merit or Excellence depth.

Vocabulary

Algorithm, input, output, linear search, binary search, sorted, unsorted, comparison, pseudocode, trace table, efficiency, input size, complexity.

Curriculum links

• Year 13 Digital Technologies: computational thinking, algorithmic thinking, efficiency, complexity and tractability.
• NCEA Digital Technologies AS91908: Analyse an area of computer science, with a focus on the 2026 external examination topic Complexity and tractability.
• Key Competencies: thinking; managing self; participating and contributing; relating to others.

Authoritative reference: NZQA 2026 Assessment Specifications for AS91908

Lesson structure (60 minutes)

1. 0–7 min · Unplugged starter. Display the hook and starter slides and ask, “How could you find one name quickly in a mixed-up list of 100 names?” Give one student a secretly chosen target and ask the class to find it by checking objects or students one at a time. Students observe the number of checks, then suggest ways to improve the process. Establish that an algorithm is a repeatable set of instructions and record students’ existing ideas.

2. 7–17 min · Explicit modelling. Use the search comparison slides to model linear search on the list 4, 9, 2, 7, 5, 1, looking for 7. Then model binary search on the sorted list 1, 2, 4, 5, 7, 9, explaining that each comparison eliminates approximately half the remaining items. Students predict the next item checked before each teacher reveal. Emphasise that binary search cannot be used reliably on unsorted data. Introduce efficiency informally: more input means more work, and the growth in work matters.

3. 17–30 min · Pair search investigation. Distribute the search and trace worksheet and give each pair a set of numbered cards or classroom objects labelled with numbers. Students complete a linear search for a target, recording every comparison, then order the items and repeat using binary search. Pairs compare the number of comparisons and answer: “Which method was better here, and what condition made it possible?” Circulate and check that students do not discard items arbitrarily during linear search or use binary search before sorting.

4. 30–42 min · Sorting as preparation. Demonstrate selection sort conceptually with six number cards: find the smallest remaining value, swap it into the next position, and repeat. Show the matching short pseudocode on the sorting demonstration slides. Avoid requiring memorisation. In groups of three or four, students sort a new set of cards, with one student acting as the computer, one recording comparisons, and others checking the rule. Students annotate the worksheet with one reason sorting is useful and one possible cost of sorting.

5. 42–53 min · Trace-table and problem-solving task. Students complete the pseudocode trace on the search and trace worksheet for a binary search of a sorted list. They record the list, target, middle position, comparison, and remaining search range after each step. Students then answer a challenge question: “Why might a computer need a different strategy when a list grows from 10 items to one million items?” Pause for a whole-class check. Connect this to the Field Guide idea that some problems become impractical as input size grows; a faster computer does not always solve a poor strategy.

6. 53–60 min · Plenary and exit ticket. Return to the plenary and exit-ticket slides. Students individually complete three responses on the worksheet: define an algorithm in their own words; explain why binary search needs sorted data; and state one misconception or correction they made today. Invite two students to share contrasting answers, then collect responses to identify next steps.

Resources

• Authoritative reference: NZQA 2026 Assessment Specifications for AS91908
• Teacher reference: Computer Science Field Guide chapter on complexity and tractability
• Searching and sorting introduction deck
• the search and trace worksheet
• Sets of numbered cards, sticky notes or labelled classroom objects
• Whiteboard and markers
• Timer
• Student devices, if completing the optional coding follow-up
• Prepared linear-search and selection-sort pseudocode

Assessment

• During the starter, listen for whether students describe a repeatable process rather than an informal guess.
• During pair and group work, check comparison counts, sorted order, and trace-table accuracy; ask students to justify why a search range can be discarded.
• Use the exit ticket to assess algorithm vocabulary, the sorted-data requirement and understanding that input size affects efficiency.

Differentiation

• Support students with a partially completed trace table, numbered positions rather than ambiguous indexes, a worked linear-search example and sentence starters such as “Binary search is faster when…” and “Sorting is necessary because…”.
• Pair students strategically and allow students to physically move cards while a partner records; read pseudocode aloud and use high-contrast, uncluttered worksheets for students with literacy or processing needs.
• For EAL learners, provide a small word bank with icons for input, target, middle, compare and discard; accept oral explanations before written responses.
• Extend confident students by asking them to design a worst-case example for each search, compare selection sort with bubble sort conceptually, or predict how the number of comparisons changes as the list doubles.

Common misconceptions

• Binary search does not mean checking every second item; it checks the middle of the current sorted range.
• Sorting is not the same as searching; sorting rearranges data, while searching locates a target.
• Binary search is not automatically better if the data is unsorted or if sorting costs more than the search saves.
• A correct algorithm is not necessarily efficient; computational difficulty can grow rapidly with input size.

Homework or coding follow-up

Students may translate the linear-search or binary-search pseudocode into Python, test it on lists of 10, 100 and 1,000 values, and record the number of comparisons. They should not claim that timing alone proves efficiency; they should explain what was measured and how input size affected the result.