Paper 1 Search and Sort Answers

These answers correspond to Paper 1 Search and Sort Drills.

Answer 1: Linear Search Trace

Step	index	item	result
1	0	17	not found
2	1	4	not found
3	2	29	not found
4	3	8	not found
5	4	13	found; return 4

Mark points:

• checks items from left to right;
• shows the target is not at indexes 0, 1, 2, or 3;
• identifies index 4 as the found position;
• states the returned index is 4.

Common weak answer:

• returning the target value 13 instead of the index 4.

Answer 2: Linear Search Absent Case

1. Four items are checked.
2. -1 is returned.
3. If the target is absent, the loop finishes without returning inside the loop. The final return gives a clear not-found result.

Mark points:

• all four items are inspected;
• standard absent result is -1;
• explains that no in-loop return happens when the target is absent;
• links the final return to a clear not-found outcome.

Common weak answer:

• saying the algorithm should return the last index. The last index was checked, but it did not contain the target.

Answer 3: Binary Search Trace

Step	low	high	mid	middle value	action
1	0	8	4	25	target is larger, set low to 5
2	5	8	6	44	target found at index 6

Mark points:

• initialises low = 0 and high = 8;
• calculates first mid = 4;
• updates low to 5 because 44 > 25;
• calculates second mid = 6 and finds 44.

Common weak answer:

• using the middle value 25 as the new low instead of using the index update mid + 1.

Answer 4: Preconditions and Complexity

1. Binary search requires sorted data, but [14, 2, 19, 7, 31, 11] is unsorted.
2. Linear search worst-case time complexity is $O(n)$.
3. Binary search worst-case time complexity on a sorted list is $O(\log n)$.
4. For a very small unsorted list, linear search may be suitable because it is simple and avoids the extra step of sorting before a single binary search.

Mark points:

• states the sorted-list precondition;
• gives $O(n)$ for linear search;
• gives $O(\log n)$ for binary search;
• gives a practical reason related to small input size.

Common weak answer:

• saying binary search is always better because it is faster. Binary search is only valid when the data is sorted.

Answer 5: Bubble Sort Trace

Start:

[6, 2, 9, 1, 5]

After pass 1:

[2, 6, 1, 5, 9]

After pass 2:

[2, 1, 5, 6, 9]

Explanation:

During a pass, adjacent out-of-order values are swapped. A larger value keeps moving right when it is compared with smaller neighbours, so the largest value in the unsorted section is pushed to the end of that section.

Mark points:

• correct list after pass 1;
• correct list after pass 2;
• mentions adjacent comparisons and swaps;
• explains why larger values move right through repeated swaps.

Common weak answer:

• showing only the final sorted list instead of the list after each requested pass.

Answer 6: Insertion Sort Trace

After inserting 3:

[3, 7, 5, 2]

After inserting 5:

[3, 5, 7, 2]

Reasoning:

• The initial sorted section is [7].
• To insert 3, shift 7 right and place 3 at the front.
• To insert 5, shift 7 right and place 5 after 3.

Mark points:

• recognises the sorted section grows from the left;
• correctly places 3 before 7;
• correctly places 5 between 3 and 7;
• leaves the not-yet-inserted 2 at the end after the second insertion.

Answer 7: Merge Sort Idea

Split-down:

[8, 1, 6, 3]
[8, 1] [6, 3]
[8] [1] [6] [3]

Merge-up:

[1, 8] [3, 6]
[1, 3, 6, 8]

Worst-case time complexity: $O(n\log n)$.

Mark points:

• splits the list into two halves;
• continues until one-item lists;
• merges [8] and [1] as [1, 8];
• merges [6] and [3] as [3, 6];
• merges the two sorted sublists correctly;
• states $O(n\log n)$.

Common weak answer:

• saying merge sort is complete after splitting. The ordering is rebuilt during merging.

Answer 8: Quicksort Partition

1. Pivot: 5.
2. less = [2, 1], equal = [5], greater = [9, 7].
3. Quicksort can be $O(n^2)$ when pivot choices repeatedly create highly unbalanced partitions, so each recursive call reduces the problem by only a small amount.

Mark points:

• identifies the first value as the pivot;
• places values smaller than 5 into less;
• places the pivot value 5 into equal;
• places values greater than 5 into greater;
• explains unbalanced partitions as the reason for the worst case;
• links the poor worst case to recursive calls reducing the problem by only a small amount each time.

Common weak answer:

• claiming quicksort is always $O(n\log n)$. That is not the worst-case guarantee.

Answer 9: Hash Table Search

1. The situation is called a collision.
2. If many keys share a bucket, the search may need to scan several collided keys inside that bucket. In the worst case, many or all keys may be in one bucket, so lookup can degrade to $O(n)$.
3. A good hash function should be deterministic, fast to compute, spread keys evenly, minimise collisions, or generate indexes within the table range.

Mark points:

• names collision;
• explains bucket scanning;
• links collisions to slower worst-case search;
• states one valid hash-function feature.

Common weak answer:

• saying a good hash function guarantees no collisions. It should reduce collisions, but collisions are still possible.

Answer 10: Error in Binary Search

Possible corrections:

• Use WHILE low <= high so the final remaining index is checked.
• When the target is larger, use low <- mid + 1.
• When the target is smaller, use high <- mid - 1.

Why these matter:

• low < high may stop before checking the last possible index.
• Updating to mid can leave the boundary unchanged, causing repeated checks or an infinite loop.
• Moving to mid + 1 or mid - 1 excludes the middle item that has already been checked.

Mark points:

• identifies the loop condition weakness;
• corrects the loop condition;
• identifies at least one boundary update weakness;
• gives the correct + 1 or - 1 update.