题目

下列选项中，不能构成折半查找中关键字比较序列的是()。

错因

B

500 → 450 → 200 → 180 是一路严格递减——感觉太"巧"或"线性"，怀疑不像折半查找。但折半查找完全可以一路向左走，每次新 mid 都比上一次小（在足够大的数组里可以构造出来，如 n=15、各值在适当下标）。这不是禁忌，是合法路径。

C

180 → 500 → 200 → 450 出现了明显的"折返"（180 之后忽大、再忽小、再忽大），看起来不像二分。但折半查找的判定树就是一棵 BST，从根往下走时每跨一层值就在新区间里，左右选择会让"被比较的值"出现锯齿。180 是 root（向右走全部），500 是右子树的某个比较节点，200、450 是后续子树——只要节点权值在判定树里相对位置合法即可。本题里区间约束 (180, ∞) → (180, 500) → (200, 500) 一路自洽。

D

180 → 200 → 500 → 450 类似 C，看起来不像二分。其实"先升后降"完全允许：根 180、右子是 200、200 的右子是 500、500 的左子是 450，区间约束 (180, ∞) → (200, ∞) → (200, 500)，每一步新比较的值都落在合法区间内。

总解析

判定原理：折半查找的"比较序列"= 在判定树（一棵特殊的 BST）里从根到某个节点的一条路径上的关键字。判断一个序列合不合法，最快的方法是维护当前可行区间 ：

• 初始
• 比较 后：
  • 若下一步往左子（即下一个 ）：新区间
  • 若下一步往右子（即 ）：新区间
• 任意时刻，下一个被比较的 必须落在当前区间 内；否则非法。

逐项检验：

A：500, 200, 450, 180

步骤	比较	走向	新区间
1	500	—
2	200 < 500	左
3	450 > 200	右
4	180 < 450	左 → 应在	❌ 180 < 200，不在区间

第 4 步 180 落到了禁区 (200, 450) 外——既然第 3 步走的是 200 的右子树，那以后所有节点都必须 > 200，可 180 < 200，矛盾。A 非法。

B：500, 450, 200, 180

每一步都往左：区间逐步收紧为 ，每个新值都 < 上界，全部合法。 ✅

C：180, 500, 200, 450

步骤	比较	走向	新区间
1	180	—
2	500 > 180	右
3	200 < 500	左
4	450 > 200	右	✅

每一步都在合法区间，C 合法。

D：180, 200, 500, 450

步骤	比较	走向	新区间
1	180	—
2	200 > 180	右
3	500 > 200	右
4	450 < 500	左	✅

每步合法，D 合法。

解题套路：拿到选项就维护"区间 (L, R)"四个字。看哪个选项最先跳出区间，就是答案。这个套路在折半查找比较序列、BST 路径合法性的题里通杀。

直觉：A 之所以错，本质是**"先承诺 > 200 后又拿出 180"**——折半查找的判定树是 BST，一旦走进右子树，就再也不能用一个比父节点小的值。任何"承诺后反悔"的序列都非法。

最终答案是 A（500, 200, 450, 180）。