Detect impossible binary search comparison sequence
Problem Description
Consider the fundamental binary search algorithm applied to a sorted array of numeric keys. We are given a set of specific keys: 180, 200, 450, and 500, which are ordered such that 180 < 200 < 450 < 500.
Your task is to analyze several proposed sequences of key values that the binary search algorithm might compare against a search target during a single execution. For each sequence, determine if it could realistically occur for some target value in some sorted array containing the specified keys.
Identify which of the following comparison sequences cannot be generated by a valid binary search execution:
- A.
500, 200, 450, 180 - B.
500, 450, 200, 180 - C.
180, 500, 200, 450 - D.
180, 200, 500, 450
AI interview prep
Core dilemma
Precisely identifying and articulating the invariant properties of binary search that govern the valid sequence of comparisons, and using this understanding to detect violations.
2 tradeoffs and 2 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Detect impossible binary search comparison sequence
Problem Description
Consider the fundamental binary search algorithm applied to a sorted array of numeric keys. We are given a set of specific keys: 180, 200, 450, and 500, which are ordered such that 180 < 200 < 450 < 500.
Your task is to analyze several proposed sequences of key values that the binary search algorithm might compare against a search target during a single execution. For each sequence, determine if it could realistically occur for some target value in some sorted array containing the specified keys.
Identify which of the following comparison sequences cannot be generated by a valid binary search execution:
- A.
500, 200, 450, 180 - B.
500, 450, 200, 180 - C.
180, 500, 200, 450 - D.
180, 200, 500, 450