Computer Science
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.
Python Searching
4 Likes
Answer
list1 = [1, -2, 32, 8, 17, 19, 42, 13, 0, 44]
n = 10
1. Item = 8
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| elements | 1 | -2 | 32 | 8 | 17 | 19 | 42 | 13 | 0 | 44 |
The step-by-step process of linear search is as follows:
| index | index < n | list1[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 |
Therefore, for item 8, linear search returns 3 (index).
2. Item = 1
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| elements | 1 | -2 | 32 | 8 | 17 | 19 | 42 | 13 | 0 | 44 |
The step-by-step process of linear search is as follows:
| index | index < n | list1[index] = key | index = index + 1 |
|---|---|---|---|
| 0 | 0 < 10 ? Yes | 1 = 1 ? Yes |
Therefore, for item 1, linear search returns 0 (index).
3. Item = 99
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| elements | 1 | -2 | 32 | 8 | 17 | 19 | 42 | 13 | 0 | 44 |
The step-by-step process of linear search is as follows:
| index | index < n | list1[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 = ? No | 10 |
| 10 | 10 < 10 ? No |
Since the item 99 is not found in the list, the linear search algorithm returns -1.
4. Item = 44
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| elements | 1 | -2 | 32 | 8 | 17 | 19 | 42 | 13 | 0 | 44 |
The step-by-step process of linear search is as follows:
| index | index < n | list1[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 |
Therefore, for item 44, linear search returns 9 (index).
Answered By
1 Like
Related Questions
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?
Write a program that takes as input a list having a mix of 10 negative and positive numbers and a key value. Apply linear search to find whether the key is present in the list or not. If the key is present it should display the position of the key in the list otherwise it should print an appropriate message. Run the program for at least 3 different keys and note the result.
Write a program that takes as input a list of 10 integers and a key value and applies binary search to find whether the key is present in the list or not. If the key is present it should display the position of the key in the list otherwise it should print an appropriate message. Run the program for at least 3 different key values and note the results.
Following is a list of unsorted/unordered numbers:
[50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55, 9]- Use linear search to determine the position of 1, 5, 55 and 99 in the list. Also note the number of key comparisons required to find each of these numbers in the list.
- Use a Python function to sort/arrange the list in ascending order.
- Again, use linear search to determine the position of 1, 5, 55 and 99 in the list and note the number of key comparisons required to find these numbers in the list.
- Use binary search to determine the position of 1, 5, 55 and 99 in the sorted list. Record the number of iterations required in each case.