Use the linear search program to search the key with value 8 in the list having duplicate values such as [42, -2, 32, 8, 17, 19, 42, 13, 8, 44]. What is the position returned? What does this mean?
When linear search is applied to find the key 8 in the list [42, -2, 32, 8, 17, 19, 42, 13, 8, 44], the algorithm compares each element sequentially from the beginning. It compares 42, -2, 32, and then finds 8 at position 4. The position returned is position 4.
This means that when there are duplicate values in the list, the linear search algorithm returns the position of the first occurrence of the key. The algorithm stops searching as soon as it finds a match and does not continue to find other occurrences of the same key. The second occurrence of 8 at position 9 is never checked because the search terminates after finding the first match.
Explanation
The textbook context demonstrates through Tables 6.2 and 6.4 that linear search compares elements one by one from the start and stops immediately upon finding a match. The question tests whether students understand that linear search only returns the first occurrence when duplicates exist. The algorithm makes 4 comparisons (positions 1-4) and returns position 4, ignoring the second 8 at position 9.
Solution Steps
Step 1: Start linear search from index 0 (position 1)
Step 2: Compare 42 with 8 → No match, move to next
Step 3: Compare -2 with 8 → No match, move to next
Step 4: Compare 32 with 8 → No match, move to next
Step 5: Compare 8 with 8 → Match found at position 4
Step 6: Return position 4 and terminate search