試験Foundations-of-Computer-Science トピック1 問題47 スレッド

Binary search is designed for searching in asorted (ordered) sequence. Its efficiency comes from repeatedly comparing the target to the middle element and discarding half of the remaining search space. This halving logic only works when the data is ordered, because the algorithm relies on the guarantee that all elements on one side of the midpoint are smaller (or larger) than the midpoint. In textbooks, this requirement is stated explicitly: binary search assumes the collection is sorted according to the same ordering used for comparisons.
An "ordered list" is therefore the correct focus among the options. Binary search can be implemented on arrays or other random-access structures where you can quickly access the middle element by index. While you can conceptually perform binary search on a linked list, it becomes inefficient because finding the middle requires linear traversal, losing the O(log n) advantage. Stacks and queues are not appropriate because they restrict access to ends only (LIFO for stacks, FIFO for queues), preventing direct access to the midpoint and making the binary search strategy infeasible.
Thus, the central requirement for binary search is a sorted/ordered sequence, typically supporting efficient indexing, which is why the correct choice is an ordered list.