Question

a. Write a version of the sequential search algorithm that can be used to search a sorted list. b. Consider the following list: 51217354665788593110115 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 or not? (Recall that comparisons mean item comparisons, not index comparisons.) i. 35 ii. 60 iii. 78 iv. 120

Short answer

35: 7 comparisons; 60: 9 comparisons; 78: 10 comparisons; 120: 13 comparisons.

Step-by-step solution

Understanding the sequential search on sorted lists

A sequential search on a sorted list means that we can terminate the search early if we encounter any number larger than the one we are searching for. This is because the list is sorted, so any larger number implies the target is not in the list.

Look at the sorted list

First, sort the provided list of numbers. The original list is: 5, 12, 17, 3, 54, 6, 65, 78, 85, 93, 11, 0, 115. After sorting, the list is: 0, 3, 5, 6, 11, 12, 17, 54, 65, 78, 85, 93, 115.

Search for the number 35

Sequentially search for 35 in the sorted list: 0, 3, 5, 6, 11, 12, 17, 54, 65, 78, 85, 93, 115. Compare against each number until encountering 54. Since 54 > 35, stop searching. Total comparisons: 7.

Search for the number 60

Sequentially search for 60 in the sorted list. Compare against: 0, 3, 5, 6, 11, 12, 17, 54, 65. Stop at 65, as 65 > 60. Total comparisons: 9.

Search for the number 78

Sequentially search for 78 in the sorted list. Compare against each number until finding 78. Total comparisons: 10.

Search for the number 120

Sequentially search for 120 in the sorted list. Compare all numbers up to 115. Since 115 is the maximum and less than 120, the search ends. Total comparisons: 13.

Key concepts

Algorithm Design

Algorithm design is the process of defining a step-by-step procedure to solve a particular problem. When designing an algorithm, it's important to consider the problem carefully before deciding on a solution strategy. In our case, we need an algorithm for sequential search in a sorted list.

The sequential search algorithm is very simple and works by checking each element in the list one by one. If it finds the item we're looking for, the search stops, and we have a successful search. If it reaches the end of the list without finding the item, the search is unsuccessful.

To design a sequential search algorithm specifically for a sorted list, we can introduce an improvement: if we encounter a number that is larger than our target number, we know that our target is not in the list. This allows us to stop the search early, saving time and resources. The list being sorted is key to this optimization, adding efficiency to the standard sequential search algorithm.

Sorted Lists

A sorted list is simply a list where the elements are arranged in a specific order. Usually, this order is ascending numerical order for numbers, which means that each number is equal to or greater than the one before it.

In a sorted list, we can leverage the arrangement to make searching more efficient. This is because once we encounter an element in the list that is greater than the target number, we can conclude that the target number is not present in the list. Hence, the sequential search algorithm takes advantage of this perfectly arranged data to optimize search operations.

To use a sorted list effectively, it's important first to ensure that the list is appropriately sorted before any search operations are performed. For example, in our exercise, sorting turned the original unordered list into: 0, 3, 5, 6, 11, 12, 17, 54, 65, 78, 85, 93, 115.

Item Comparisons

Item comparisons are at the heart of the sequential search algorithm. This involves checking each item in the list to see if it matches the item you're searching for.

The number of comparisons made can indicate the algorithm's efficiency. Fewer comparisons generally mean a faster and more efficient search. In a normal sequential search, every item must be checked against the target, which can be time-consuming.

However, when dealing with a sorted list, item comparisons can be reduced. If we encounter a number larger than the one we're searching for, we can stop comparing further, since any subsequent numbers will also be larger. This is a significant improvement because it allows the search to be terminated early.

Early Termination in Search

Early termination in search is a feature that enhances the efficiency of search algorithms when used with sorted lists. Unlike searching through an unsorted list, where each item must be examined, a sorted list allows the search process to end sooner under specific conditions.

In a sorted list, we can terminate the search as soon as we encounter an item greater than the target value. This means fewer comparisons are required, minimizing unnecessary checks and saving time.

For example, when searching for the number 35 in our sorted list, the search stops at 54, as it is the first number greater than 35. Similarly, while searching for 60, the search ends at 65. This demonstrates the practical advantage of early termination, reducing the number of comparisons needed for each search operation.