Question

Mark the following statements as true or false. a. \(\quad\) A sequential search of a list assumes that the list is in ascending order. b. \(\quad\) A binary search of a list assumes that the list is sorted. c. \(A\) binary search is faster on ordered lists and slower on unordered lists. d. \(A\) binary search is faster on large lists, but a sequential search is faster on small lists.

Short answer

a. False; b. True; c. True; d. True.

Step-by-step solution

Evaluate Statement a

A sequential search, also known as a linear search, does not assume that the list is in ascending order. It simply checks each element in sequence to find the desired value. Therefore, the statement that a sequential search assumes the list is in ascending order is false.

Evaluate Statement b

A binary search requires the list to be sorted (either in ascending or descending order) because it repeatedly divides the search interval in half and compares the target value to the middle element. Thus, without a sorted list, a binary search would be impossible. Hence, the statement that a binary search assumes the list is sorted is true.

Evaluate Statement c

A binary search cannot be performed on an unordered list by definition; it only works on ordered lists. Therefore, it is incorrect to say a binary search is slower on unordered lists because it cannot be applied at all. Thus, this statement is true in terms of performance: binary search is inherently faster on ordered lists and not applicable on unordered lists.

Evaluate Statement d

Binary searches are generally faster on large lists due to their logarithmic time complexity, \(O(\log n)\), compared to a sequential search's linear time complexity, \(O(n)\). On very small lists, however, the constant factors involved in setting up a binary search may make a sequential search faster. Therefore, this statement is true—it correctly reflects that binary search is faster for large lists, while sequential search can be faster for small lists.

Key concepts

Sequential Search

Sequential search, also known as linear search, is the simplest search algorithm. It examines each element in the list one by one until the required element is found or the end of the list is reached. This method does not assume that the array or list is in any particular order.

Here's how sequential search works:

• The search starts at the beginning of the list.
• Each element is checked sequentially.
• The process continues until the desired element is found.
• If the end of the list is reached without finding the element, it's concluded that the element is not present.

Since a sequential search does not rely on the list being sorted, it is quite straightforward and versatile for any unsorted collection of items. However, its downside is the time taken to complete the search, especially in large lists, as it exhibits linear time complexity, expressed as \(O(n)\). This means the time to find an element increases linearly with the size of the list. For smaller lists, sequential search works efficiently, but as the list size grows, its efficiency diminishes when compared to more advanced search algorithms.

Binary Search

Binary search is a more advanced algorithm designed to work on sorted lists. Unlike sequential search, binary search is much faster due to its logarithmic nature. However, this speed comes with the prerequisite that the list must already be ordered.

Here's how binary search works:

• The search begins by determining the middle element of the list.
• If this middle element is equal to the targeted value, the search is complete.
• If the targeted value is less than the middle element, the search focuses on the lower half of the list.
• If the targeted value is greater, it turns its attention to the upper half.
• This process repeats, halving the list with each iteration, until the item is found or the sublist reduces to zero.

Binary search is particularly efficient due to its time complexity of \(O(\log n)\), meaning that even as the list grows, the number of necessary comparisons increases only logarithmically. This makes binary search a preferred choice for working with large, sorted datasets.

Algorithm Complexity

Understanding algorithm complexity is crucial when selecting the appropriate search method for a task. It essentially measures the efficiency of an algorithm, typically represented in Big O notation. This notation helps to express the worst-case scenario in terms of time (or space) required for an algorithm to complete.For search algorithms:

• Sequential Search (or Linear Search) has a time complexity of \(O(n)\). This means that if a list doubles in size, the search time also doubles, as each element must be checked one by one.


• Binary Search, on the other hand, has a time complexity of \(O(\log n)\). This represents a much smaller increase in time as the list size increases, assuming the list is sorted.

When comparing both, binary search far outpaces sequential search on large datasets because it reduces the problem size significantly with each step. However, on smaller datasets or unsorted ones, the simplicity and minimal overhead of sequential search might make it more desirable. Choosing which search algorithm to use depends on factors like list size, whether it's sorted, and the required efficiency.