Advanced Placement (AP) Computer Science

What is required for binary search to function properly?

1. The list must be unsorted

2. The list must contain unique elements

3. The list must be sorted in order

4. The list must be small in size

The correct answer is: The list must be sorted in order

For binary search to function properly, the list must be sorted in order. This is essential because binary search works by repeatedly dividing the search interval in half and eliminating the portion of the list that cannot contain the target value. If the list is not sorted, the algorithm cannot make accurate decisions about which half of the list to discard during each step of the search process. In a sorted list, the algorithm can efficiently determine whether to search in the left or the right half based on the comparison between the middle element and the target value. This characteristic allows binary search to achieve a logarithmic time complexity, making it significantly faster than linear search methods for large datasets. Having unique elements, while beneficial in some contexts, is not a requirement for binary search to function; it can handle duplicate values as long as the list remains sorted. Similarly, the size of the list does not impose a restriction on binary search; it can operate on smaller or larger lists as long as they are sorted.