Question

Linear search works best on:

• A. Sorted list only
• B. Unsorted list
• C. Binary tree
• D. Graph

Hint:

If a list is already sorted, always prefer binary search over linear search because its time complexity is significantly lower. For unsorted lists, linear search is the standard choice.

Answer 1

The Correct Option is B

Step 1: Understanding the Question:
The question aims to identify the data structure configuration or state where linear search is the most suitable or standard searching method.

Step 2: Detailed Explanation:
$\bullet$ Linear search (or sequential search) is a fundamental algorithm that checks each element of a list sequentially until a match is found or the end is reached.
$\bullet$ In a sorted list, highly efficient algorithms like binary search can find elements in logarithmic time, \(O(\log n)\), making linear search inefficient there.
$\bullet$ However, when a list is unsorted, there is no inherent order to exploit, meaning we cannot skip any elements using binary search or other divide-and-conquer methods.
$\bullet$ Thus, for an unsorted list, a sequential scan using linear search is the only straightforward and direct option available.
$\bullet$ While its worst-case time complexity is \(O(n)\) regardless of the sorting status, linear search is considered the best choice for unsorted or small datasets where sorting overhead is not justified.
$\bullet$ Binary trees and graphs require specialized traversal algorithms like Depth First Search (DFS) or Breadth First Search (BFS) rather than simple linear search.

Step 3: Final Answer:
Therefore, linear search is best suited for an unsorted list, which corresponds to option (B).