Advanced Placement (AP) Computer Science

How does linear search compare to binary search?

1. Linear search is faster than binary search

2. Binary search requires a sorted list, while linear search does not

3. Linear search can search sorted lists more efficiently

4. Binary search is the only method that guarantees finding an item

The correct answer is: Binary search requires a sorted list, while linear search does not

Binary search is a searching algorithm that operates on sorted lists by dividing the search interval in half repeatedly, which allows it to quickly narrow down the potential location of the desired item. This method requires the list to be sorted beforehand, as it takes advantage of the order to efficiently eliminate half of the remaining elements in each step. In contrast, a linear search operates by checking each element in the list sequentially until the desired item is found or the end of the list is reached. The linear search does not require the list to be sorted, making it versatile for searching through unordered collections of data. The correct answer highlights this critical distinction: binary search relies on the list being sorted, while linear search does not have this requirement. This fundamental difference dictates when to use each algorithm based on the data at hand.