Using linear search determine the position of 8, 1, 99 and 44 in the list: [1, -2, 32, 8, 17, 19, 42, 13, 0, 44]. Draw a detailed table showing the values of the variables and the decisions taken in each pass of linear search.
Given List: [1, -2, 32, 8, 17, 19, 42, 13, 0, 44] with n = 10 elements.
Search for Key = 8:
| index | index < n | numList[index] = key | index = index + 1 |
|---|---|---|---|
| 0 | 0 < 10? Yes | 1 = 8? No | 1 |
| 1 | 1 < 10? Yes | -2 = 8? No | 2 |
| 2 | 2 < 10? Yes | 32 = 8? No | 3 |
| 3 | 3 < 10? Yes | 8 = 8? Yes |
Element 8 found at position 4 after 4 comparisons.
Search for Key = 1:
| index | index < n | numList[index] = key | index = index + 1 |
|---|---|---|---|
| 0 | 0 < 10? Yes | 1 = 1? Yes |
Element 1 found at position 1 after 1 comparison (minimum work).
Search for Key = 99:
| index | index < n | numList[index] = key | index = index + 1 |
|---|---|---|---|
| 0 | 0 < 10? Yes | 1 = 99? No | 1 |
| 1 | 1 < 10? Yes | -2 = 99? No | 2 |
| 2 | 2 < 10? Yes | 32 = 99? No | 3 |
| 3 | 3 < 10? Yes | 8 = 99? No | 4 |
| 4 | 4 < 10? Yes | 17 = 99? No | 5 |
| 5 | 5 < 10? Yes | 19 = 99? No | 6 |
| 6 | 6 < 10? Yes | 42 = 99? No | 7 |
| 7 | 7 < 10? Yes | 13 = 99? No | 8 |
| 8 | 8 < 10? Yes | 0 = 99? No | 9 |
| 9 | 9 < 10? Yes | 44 = 99? No | 10 |
| 10 | 10 < 10? No |
Element 99 not found in the list after 10 comparisons.
Search for Key = 44:
| index | index < n | numList[index] = key | index = index + 1 |
|---|---|---|---|
| 0 | 0 < 10? Yes | 1 = 44? No | 1 |
| 1 | 1 < 10? Yes | -2 = 44? No | 2 |
| 2 | 2 < 10? Yes | 32 = 44? No | 3 |
| 3 | 3 < 10? Yes | 8 = 44? No | 4 |
| 4 | 4 < 10? Yes | 17 = 44? No | 5 |
| 5 | 5 < 10? Yes | 19 = 44? No | 6 |
| 6 | 6 < 10? Yes | 42 = 44? No | 7 |
| 7 | 7 < 10? Yes | 13 = 44? No | 8 |
| 8 | 8 < 10? Yes | 0 = 44? No | 9 |
| 9 | 9 < 10? Yes | 44 = 44? Yes |
Element 44 found at position 10 after 10 comparisons (maximum work).
Explanation
This question tests the student's understanding of linear search algorithm execution. The algorithm compares each element sequentially from index 0 until the key is found or the list ends. When key is at position 1 (index 0), only 1 comparison is needed - this is the minimum work. When key is at the last position or not found, n comparisons are needed - this is the maximum work. The tables follow the format shown in the textbook (Tables 6.2, 6.4) where each row represents one pass showing the index value, loop condition check, comparison result, and index increment.
Solution Steps
Step 1: Identify the list [1, -2, 32, 8, 17, 19, 42, 13, 0, 44] with n=10 elements and indices 0-9.
Step 2: For key=8, traverse from index 0 to 3, comparing each element until match found at index 3 (position 4).
Step 3: For key=1, match found immediately at index 0 (position 1) - minimum comparisons.
Step 4: For key=99, traverse entire list without finding, exit when index=10 fails condition index<n.
Step 5: For key=44, traverse entire list, match found at last index 9 (position 10) - maximum comparisons.