Question 1
A linear search is performed on the following unsorted list for the target value `"Maple"`: ``` trees = ["Oak", "Pine", "Birch", "Maple", "Cedar", "Elm"] ``` How many comparisons are made before the target is found, and what is the value of `foundIndex` at termination?No clue? Show me the answer
Correct answerCorrect!
IncorrectStep-by-step walkthrough
Choose a solution method
Method #1Approach 1Step 1: Set up initial state
foundIndex = -1, and we begin at index 0. The target is "Maple".
Step 2: Trace each comparison
- i=0: "Oak" ≠ "Maple" → no match
- i=1: "Pine" ≠ "Maple" → no match
- i=2: "Birch" ≠ "Maple" → no match
- i=3: "Maple" == "Maple" → match found, foundIndex = 3, BREAK
Step 3: Count comparisons
The algorithm performed comparisons at indices 0, 1, 2, and 3 — that is 4 comparisons in total before (and including) the match.
Step 4: State the result
foundIndex = 3 (index of "Maple") and 4 comparisons were made. The correct answer is: 4 comparisons; foundIndex = 3.
Method #2Approach 2Step 1: Identify what is being asked
We need both the number of comparisons and the final value of foundIndex. foundIndex stores the index where the target was found.
Step 2: Eliminate '3 comparisons; foundIndex = 3'
"Maple" is at index 3, so the algorithm checks indices 0, 1, 2, AND 3 — that is 4 comparisons, not 3. Eliminated.
Step 3: Eliminate options with foundIndex = 4
"Maple" is at index 3 in the list (0-based indexing). foundIndex = 4 would mean it was found at "Cedar", which is wrong. Both options with foundIndex = 4 are eliminated.
Step 4: Select the correct answer
The only remaining option is 4 comparisons; foundIndex = 3, which correctly reflects 4 checks (indices 0–3) and the match at index 3.
Question 2
A binary search is performed on the following sorted list for the target `45`: ``` nums = [5, 12, 18, 23, 31, 45, 67, 89, 102] ``` Indices: 0, 1, 2, 3, 4, 5, 6, 7, 8 What are the values of `low`, `high`, and `mid` in the first iteration?No clue? Show me the answer
Correct answerCorrect!IncorrectStep-by-step walkthrough
Choose a solution method
Method #1Approach 1Step 1: Initialise low and high
Binary search begins with low = 0 (first index) and high = length(list) - 1 = 9 - 1 = 8 (last index).
Step 2: Calculate mid
Step 3: State first iteration values
In the first iteration: low = 0, high = 8, mid = 4. The element at index 4 is 31, which is less than 45, so low would be updated to 5 in the next iteration.
Method #2Approach 2Step 1: Identify the initialisation rules
Binary search always starts with low = 0 and high = length - 1. The list has 9 elements, so high = 8.
Step 2: Eliminate 'low = 0, high = 9, mid = 4'
high should be length - 1 = 8, not 9. Using high = 9 would be an off-by-one error. Eliminated.
Step 3: Eliminate 'low = 1, high = 8, mid = 4'
low starts at 0, not 1. Starting at 1 would skip the first element. Eliminated.
Step 4: Eliminate 'low = 0, high = 8, mid = 5'
, not 5. mid = 5 would only result from rounding up, but integer division rounds down. Eliminated.
Step 5: Select the correct answer
low = 0, high = 8, mid = 4 is the only option consistent with correct binary search initialisation and midpoint calculation.