Question

a. Write a version of the sequential search algorithm that can be used to search a sorted list. b. Consider the following list: 8,12,15,27,35,48,65,77,86,94,120 Using a sequential search on ordered lists, which you designed in (a), how many comparisons are required to determine whether the following items are in the list? (Recall that comparisons mean item comparisons, not index comparisons. i. 65 ii. 8 iii. 80 iv. 125

Short answer

i. 7 comparisons ii. 1 comparison iii. 9 comparisons iv. 12 comparisons

Step-by-step solution

Understand the Sequential Search Algorithm

Sequential search examines each element in the list one-by-one until it finds the target item or reaches the end of the list. When used on a sorted list, the search can terminate early if the current element is greater than the target, reducing unnecessary comparisons.

Implement the Enhanced Sequential Search

Modify the conventional sequential search algorithm to terminate when the current element is greater than the target. Pseudocode: 1. Start from the first element. 2. Compare current element with the target. 3. If current element equals the target, record the index and stop. 4. If current element is greater than the target, stop. 5. Move to the next element and repeat steps 2-4 until end of the list.

Search for 65 in the List

1. Compare 65 with 8. (Not equal, continue) 2. Compare 65 with 12. (Not equal, continue) 3. Compare 65 with 15. (Not equal, continue) 4. Compare 65 with 27. (Not equal, continue) 5. Compare 65 with 35. (Not equal, continue) 6. Compare 65 with 48. (Not equal, continue) 7. Compare 65 with 65. (Equal, stop) Total comparisons: 7.

Search for 8 in the List

1. Compare 8 with 8. (Equal, stop) Total comparisons: 1.

Search for 80 in the List

1. Compare 80 with 8. (Not equal, continue) 2. Compare 80 with 12. (Not equal, continue) 3. Compare 80 with 15. (Not equal, continue) 4. Compare 80 with 27. (Not equal, continue) 5. Compare 80 with 35. (Not equal, continue) 6. Compare 80 with 48. (Not equal, continue) 7. Compare 80 with 65. (Not equal, continue) 8. Compare 80 with 77. (Not equal, continue) 9. Compare 80 with 86. (Greater, stop) Total comparisons: 9.

Search for 125 in the List

1. Compare 125 with 8. (Not equal, continue) 2. Compare 125 with 12. (Not equal, continue) 3. Compare 125 with 15. (Not equal, continue) 4. Compare 125 with 27. (Not equal, continue) 5. Compare 125 with 35. (Not equal, continue) 6. Compare 125 with 48. (Not equal, continue) 7. Compare 125 with 65. (Not equal, continue) 8. Compare 125 with 77. (Not equal, continue) 9. Compare 125 with 86. (Not equal, continue) 10. Compare 125 with 94. (Not equal, continue) 11. Compare 125 with 120. (Not equal, continue) 12. Compare 125 with end of list. (Stop, not found) Total comparisons: 12.

Key concepts

Algorithm Analysis

Analyzing algorithms involves understanding the efficiency and behavior of the algorithm in terms of computational resources such as time and space. When performing algorithm analysis on a sequential search, we focus on the number of comparisons, since this determines the time complexity.
Sequential search is a simple and straightforward approach where each element in a list is inspected systematically. However, in terms of efficiency, it tends to perform quite poorly on average, especially as the list size increases. For an unsorted list, the average number of comparisons needed is approximately half of the list size, making the time complexity of sequential search linear, represented as \( O(n) \), where \( n \) is the number of elements in the list.
Using the sequential search on sorted lists can slightly improve efficiency. When an element larger than the target is found, the search can conclude prematurely, potentially reducing the number of comparisons. However, even with this improvement, the worst-case time complexity remains linear. Algorithm analysis, therefore, helps identify these nuances and aids in selecting the most appropriate searching method based on list characteristics.

Sorted List Search

When searching through a sorted list, a sequential search can take advantage of the order by stopping once a number larger than the target is found. This enhancement prevents unnecessary comparisons beyond this point.
For instance, if you are carrying out a sequential search for a value of 80 in a sorted list like \( [8, 12, 15, 27, 35, 48, 65, 77, 86, 94, 120] \), the search will proceed normally until it finds 86, which is greater than 80. It then stops searching further, as we are only looking for a target not beyond this number.
This method doesn't change the underlying time complexity from \( O(n) \), but can be notably advantageous when the target value is closer to the beginning of the list or not present in the list at all. Hence, while not as fast as a binary search on sorted data, a sequential search can still provide value by leveraging the order in moderately-sized lists.

Number of Comparisons

The number of comparisons in a search algorithm is a primary metric for gauging its performance. In terms of a sequential search on a sorted list, comparisons directly correlate with how quickly we identify the target.
For example:

• Searching for 65 involves 7 comparisons, as the algorithm systematically checks each number until it finds 65.
• Searching for 8 only requires a single comparison because 8 is the first number in the list.
• Searching for 80 takes 9 comparisons, with the algorithm stopping once it encounters 86, which exceeds 80.
• In contrast, searching for 125, which is not present, involves 12 comparisons until the algorithm exhausts the entire list.

The fewer the comparisons, the better the performance, particularly significant when optimizing for speed in lists with a large number of elements. By understanding the number of comparisons, we can better appreciate the efficiency or limitations of the sequential search when applied to sorted data.