Past questions › sdd2021-q28
2021 5 marks Extended response The Software Engineering Project (Year 12) Debugging an algorithm (binary search)
NESA 2021 HSC Software Design and Development (OLD syllabus) - Section II Question 28, with NESA Marking Guidelines
A student, attempting to perform a binary search on an array called List with 7 elements, wrote the following algorithm. The algorithm contains errors. 1 | BEGIN Search 2 | low = 1 3 | high = 7 4 | found = FALSE 5 | input SearchItem 6 | WHILE found = FALSE AND high > low 7 | index = integer part of (low + high)/2 8 | IF SearchItem = List(index) THEN 9 | found = TRUE 10 | ELSE 11 | IF SearchItem < List(index) THEN 12 | high = index 13 | ELSE 14 | low = index 15 | ENDIF 16 | ENDIF 17 | ENDWHILE 18 | IF found = TRUE THEN 19 | print “Found at ”, index 20 | ELSE 21 | print “Not found” 22 | ENDIF 23 | END Search (a) | The contents of List are shown. | 3 index | 1 | 2 | 3 | 4 | 5 | 6 | 7 List | 33 | 38 | 40 | 44 | 50 | 60 | 75 Perform a desk check of the algorithm using the value 42 for SearchItem. (b) | The logic is not correct in lines 12 and 14 of the algorithm. | 2 Modify these lines so that the logic is correct.
Marking criteria
[Question 28 (a)] Criteria | Marks • Provides a substantially correct desk check, indicating a never-ending loop • Provides a partially correct desk check | 2 • Shows some understanding of desk checking | 1 Criteria | Marks • Correctly modifies both lines | 2 • Demonstrates some understanding of the problem | 1
Sample answer
Sample answer: Low | High | Found | SearchItem | Index | List(index) | Output 1 | 7 | FALSE | 42 | 4 | 44 Does not end
[Question 28 (b)] Sample answer: Line 12 | high = index –1 Line 14 | low = index +1