Detect impossible binary search comparison sequence

Think about running binary search on a sorted array of numeric keys. The choices below are candidate orders in which the algorithm might compare keys against the search target (listed by comparison order). Assume the array contains the keys 180, 200, 450, and 500, ordered as $180 < 200 < 450 < 500$. Which of the following cannot be the sequence of keys compared during one execution of binary search (for some target value) on any sorted array? Options:

• A. 500, 200, 450, 180
• B. 500, 450, 200, 180
• C. 180, 500, 200, 450
• D. 180, 200, 500, 450 Overview: This problem checks your understanding of binary search mechanics: how comparisons proceed, how the search interval is reduced, and the invariants maintained in a sorted array.