如何把业务条件抽象成二分查找的单调谓词？

简化版

很多二分题不是直接在数组里找数，而是要先把题目条件抽象成 check(x)。

如果 x 增大后，check(x) 从 false 变 true，或者从 true 变 false，就具备二分条件。

例如容量越大越容易完成、时间越长越容易完成、速度越快越容易完成。

面试时先说清楚单调谓词，再写代码，会比直接套模板更稳。

详细版

单调谓词就是返回布尔值的判断函数，并且随着 x 的变化只发生一次方向切换。

常见形式：

false false false true true true

或者：

true true true false false false

二分查找就是找这个切换点。

例如“最小容量能在 D 天内运完”：

function canShip(capacity) {
  let days = 1
  let load = 0
  for (const w of weights) {
    if (load + w > capacity) {
      days++
      load = 0
    }
    load += w
  }
  return days <= D
}

容量越大，需要天数越少，所以 canShip(capacity) 具有单调性。

完整版教学

1. 为什么要抽象单调谓词

很多面试题不会直接说“请你二分查找”。

它们会包装成业务描述：

最少几天完成任务
最小速度满足限制
最大甜度至少是多少
最小最大值怎么取

这时关键不是马上写模板，而是问：我能不能判断一个候选答案 x 是否可行？

只要可行性随 x 单调变化，二分就可以用来找临界点。

2. 单调谓词的两种方向

单调谓词通常有两类。

方向	序列形态	常见目标
false 到 true	`F F F T T`	找最小可行值
true 到 false	`T T T F F`	找最大可行值

找最小可行值时，满足条件就收缩右边界。

找最大可行值时，满足条件就收缩左边界，并注意上取中点。

3. 业务条件如何变成 check(x)

以“最小容量”为例，候选答案是容量 x。

判断函数回答：容量为 x 时，能不能在 D 天内完成？

function canFinish(x) {
  let day = 1
  let current = 0
  for (const item of items) {
    if (current + item > x) {
      day++
      current = 0
    }
    current += item
  }
  return day <= D
}

当 x 变大，每天能装的东西更多，需要的天数不会增加。

因此它是单调的。

4. 证明单调性

面试里不要只说“感觉能二分”。

要说清楚：

如果 x 可行，那么比 x 更宽松的答案也可行。
如果 x 不可行，那么比 x 更严格的答案也不可行。

对于容量题，更大的容量更宽松。

对于速度题，更快的速度更宽松。

对于最长等待时间题，更长的允许时间更宽松。

5. 单调谓词和普通比较的区别

普通二分在数组中比较 nums[mid] 和 target。

谓词二分比较的是 check(mid) 的真假。

function firstTrue(left, right) {
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (check(mid)) right = mid
    else left = mid + 1
  }
  return left
}

这使得二分能处理很多没有显式数组的问题。

6. 常见面试追问

误区：只看答案范围，不证明 check 单调。 没有单调性，二分只是碰运气。
误区：check 写得太复杂但语义不清。 判断函数应该只回答“候选答案是否可行”。
误区：把优化目标和判断目标混在一起。 二分外层负责找最优，check 只负责判定。
追问：如果 check 不是单调的怎么办？ 不能直接二分，需要换动态规划、贪心、搜索或其他方法。
追问：如何选择找 first true 还是 last true？ 看题目要最小可行值还是最大可行值。

这类追问重点考抽象能力。

7. 一个通用建模套路

可以按下面顺序思考：

1. 把问题答案命名为 x。
2. 写出 check(x) 的业务含义。
3. 判断 x 变大时 check 是更容易 true 还是更容易 false。
4. 根据方向选择 first true 或 last true 模板。

这个套路适合大多数二分答案题。

8. 面试表达模板

可以这样回答：

“我会先把优化问题改成判定问题。设候选答案为 x，写一个 check(x) 判断这个答案是否可行。然后证明 x 变大时条件只会朝一个方向变化，比如容量越大越容易完成，所以 check 从 false 变 true。这样就能用二分找第一个 true，也就是最小可行答案。”

简化版

详细版