Question

Consider the following list: 35,82,45,12,56,67,92,77 Using the sequential search as described in this chapter, how many comparisons are required to find whether the following items are in the list? (Recall that by comparisons we mean item comparisons, not index comparisons.) a. 12 b. 92 c. 65 d. 35

Short answer

a. 4 comparisons b. 8 comparisons c. 8 comparisons d. 1 comparison

Step-by-step solution

Understanding Sequential Search

Sequential search involves checking each element of a list one by one from the start to the end. If the target element is found, the search stops, and we count how many comparisons were made. If the target isn't found by the end of the list, each element will have been compared once, which means the total number of comparisons made is equal to the number of items in the list.

Finding 12

Start from the beginning of the list. First compare 12 with 35 (first element), then with 82, 45, and finally find it when comparing with 12. Thus, 4 comparisons are needed.

Finding 92

Start checking from 35, then 82, 45, 12, 56, 67, 77, and finally find 92. The total comparisons is 8, as 92 is the last element in the list.

Finding 65

Since 65 is not present in the list, you will sequentially check all elements: 35, 82, 45, 12, 56, 67, 92, and 77. 8 comparisons are made, confirming 65 is not in the list.

Finding 35

One comparison is needed, as 35 is the first element of the list.

Key concepts

Comparisons in Algorithms

Comparisons in algorithms are a crucial part of determining how an algorithm works and how efficiently it operates. In the context of a sequential search, comparisons refer to the direct examination of elements against the target element we are searching for. More formally, a 'comparison' in this algorithm is the act of checking if an element in the list is equal to the desired value. For example:

• When searching for 12, comparisons occur between 12 and each element, until a match is found.
• When looking for 92, the algorithm sequentially checks each element up to the very last one, increasing the number of comparisons.

In sequential searches, typically the number of comparisons can illustrate how efficient or inefficient the search could be, which comes into play when assessing algorithm efficiency.

Algorithm Efficiency

Algorithm efficiency describes how fast or economically an algorithm performs. The efficiency often influences the choice of which algorithm to use for a particular problem. Sequential Search, also known as a Linear Search, is often the simplest search algorithm, but it can be inefficient with larger lists because it might need to compare every single element. Consider these aspects:

• For small datasets, it works quickly and is easy to implement.
• However, as the dataset size increases, the number of comparisons grows linearly, making it less efficient.

Thus, understanding algorithm efficiency helps in deciding whether a linear search is adequate, or if more complex search algorithms could provide better performance for large datasets.

Linear Search

Linear search, often synonymous with sequential search, is a straightforward strategy for finding an element within a list. This method works by examining each item one after another, comparing them with the target value. Linear Search can be broken down as follows:

• Start from the first element and proceed sequentially.
• Check each item against the target.
• If a match is found, the search finishes.
• If no match exists, continue until reaching the end of the list.

While easy to understand and implement, linear search can become time-consuming with larger datasets, since it does not skip unnecessary checks like more advanced algorithms do.