Last reviewed
Correct answer: C. The collection must already be sorted
Explanation
The halving is only sound because the data is ordered. Sorted order is what lets one comparison speak for a whole half of the array: if the middle element already exceeds the target, every element after it exceeds the target too, so that half can go without being looked at. Strip the ordering away and that inference is simply false, which is why NIST's definition opens with a sorted array rather than mentioning it as an aside.
Handed unsorted data, binary search does not complain. It applies the same rule, walks into the wrong half, and reports the value missing or returns a meaningless index. A wrong answer with no error attached is the expensive kind, because nothing in the run points at the cause. Python's bisect functions document the same assumption. Sorting first costs more than one scan, so binary search pays off when the same collection is searched many times.
Size is beside the point: empty ranges and huge ones both work, so one element is no requirement. Unsorted inverts the actual condition. Element type is open as well, since anything with a consistent ordering will do.
Sources
“Search a sorted array by repeatedly dividing the search interval in half.”
“The return value is suitable for use as the first parameter to list.insert() assuming that a is already sorted.”
Practise 3 questions on this topic
Take Sorting & Searching — Timed Test (3 questions) — scored instantly, explanation for every question, no login.