Question

A school uses a mobile phone app to allow parents to book appointments for parents' evenings.

Parents must log in before they can use the system. They then choose to book an appointment, view all appointments already made or update their personal details. If parents choose to view their appointments, they can either view them on-screen or print them off.

Each teacher has the assessment grades for each student. These grades are stored in numerical order.

(i) The grades for one student are shown:

2, 3, 4, 5, 6, 7, 8.

Show the steps that a binary search would take to check whether the student has achieved a grade 7 in any assessment.

Your answer must refer to the grades provided.

(ii) Explain how a binary search would determine that a value does not appear in a given array.

(iii) Give one advantage of a binary search over a linear search.

Answer 1

(i) To check whether the student has achieved a grade 7 in any assessment using binary search, the steps would be as follows:

1. Identify the middle value in the array of grades. In this case, the middle value is 5.

2. Compare the middle value to 7. Since 7 is greater than 5, we know that any grade 7 would be to the right of the middle value.

3. Discard the left half of the array, including the middle value.

4. Identify the new middle value in the remaining array. In this case, the middle value is 7.

5. Compare the middle value to 7. Since 7 is equal to 7, we know that the student has achieved a grade 7 in at least one assessment.

(ii) A binary search determines that a value does not appear in a given array by continuing to divide the array in half and checking the middle value until the value is found or until there are no more values to check. If the middle value is not the value being searched for, the search can discard the half of the array that does not contain the value and continue searching the other half. If the search reaches the end of the array without finding the value, it knows that the value is not in the array.

(iii) One advantage of a binary search over a linear search is that a binary search can be much faster for large arrays. A linear search must examine each element of the array in order until it finds the value being searched for, which can be time-consuming for large arrays. In contrast, a binary search can quickly discard large portions of the array and hone in on the value being searched for, making it much more efficient for large arrays.