在软件开发中，git bisect 是定位回归 bug 的利器。传统算法通过二分查找，在 O (log n) 步内从数千个提交中锁定首个问题提交。然而，这一方法假设一个根本性前提：测试结果是确定性的 —— 给定某个提交，测试要么通过，要么失败。然而现实远比这复杂：很多测试是「间歇性失败」（flaky），同样的代码执行多次，可能时而通过，时而失败。这种不确定性来源于竞态条件、网络抖动、内存泄漏或随机数等因素。当测试结果不再可靠时，传统二分查找的「非黑即白」逻辑便失效了。

问题的本质：不确定性测试

假设一个测试在某个「坏」提交上的失败概率约为 p（0 < p < 1），而非 p = 1。如果仍然沿用传统二分查找，我们需要多少次连续通过才能「放心地」将某个提交标记为 good？如果 p = 1/2700（大约每 2700 次运行才失败一次），要让一次失败的期望时间达到可接受水平，可能需要让测试运行数千次。这意味着原本 10 步的二分查找可能需要数天甚至数周才能完成。更关键的是，即使我们在某个提交上连续通过了 2700 次，也无法保证该提交真的是「好」的 —— 我们只是运气好没遇到那一次失败。一旦后续发现该提交实际是坏的，整套二分查找的结果都需要推倒重来。

贝叶斯二分查找（Bayesian bisection）正是为解决这一痛点而设计。其核心思想是：不将测试结果视为布尔值，而是将其建模为概率分布；每执行一次测试，就根据结果更新对所有提交「可能是首个坏提交」的置信度分布，然后选择下一次测试目标，以最有效地缩小不确定区间。

概率模型与后验更新

设存在 N 个连续提交 C_0, C_1, ..., C_{N-1}，其中存在一个未知的位置 k，使得 C_i（i < k）全部为好提交，C_i（i ≥ k）全部为坏提交（但具有间歇性失败概率 p）。我们的目标是推断出 k 的后验概率分布 P (C_i 是首个坏提交)。

初始时，我们对 k 一无所知，使用均匀先验：P (C_i) = 1/N 对所有 i 成立。接下来，每次在提交 C_j 上运行测试后，使用贝叶斯定理更新分布。如果测试通过，则对于所有 i ≤ j 的提交，其为坏提交的概率需要乘以 (1-p)（因为在坏提交上测试本应有一定概率失败，既然通过了，说明它可能是好提交的置信度上升）；对于 i > j 的提交，概率不变。如果测试失败，则所有 i ≤ j 的提交不可能是首个坏提交（因为如果它们是坏提交，那么更早的提交也应该导致测试失败），因此将它们的概率置零，而 i > j 的提交概率保持不变（仅作为归一化因子）。

这个更新过程可以迭代进行。随着测试结果不断累积，概率分布会逐渐向真实的 k 值集中。值得注意的是，即便测试结果是随机的，只要我们持续更新，概率分布最终仍会收敛到真实位置 —— 这与传统二分查找「一次运气不好就失效」形成了鲜明对比。

选择下一次测试：信息增益最大化

在每一步更新完成后，我们需要决定在哪个提交上运行下一次测试。最优策略是选择「中位数」提交 —— 即使概率质量均匀分割的提交。原因在于，该提交的结果（通过或失败）将概率分布「切割」得最均匀，意味着无论结果如何，我们都能获得关于 k 位置的最大信息量。

在离散情况下，中位数提交可能有两种选择：submedian（累计概率刚好不超过 0.5 的最后一个提交）和 supermedian（累计概率刚好超过 0.5 的第一个提交）。单纯选择其中任何一种在接近收敛时都会表现不佳 —— 算法会始终执着于紧邻真实位置的一个提交。更好的策略是：比较 submedian 和 supermedian，选择迄今为止测试次数较少的那个。如果两者测试次数相同，优先选择 submedian。

进一步优化可以引入「批测试」机制：不逐次切换提交，而是每连续测试同一提交若干次后再切换。具体做法是计算 ⌊runs÷10⌋，其中 runs 是该提交已执行的测试次数，选择该值较小的提交进行测试。这样做的好处是减少了提交切换开销（每次切换可能涉及代码重新编译、环境重置等），同时在真实场景中效果显著 —— 在坏提交上，我们会看到若干次失败加若干次通过，概率分布随之精细调整。

估计失败概率 p

整个算法依赖于对测试失败概率 p 的估计。p 的存在使得分布更新能够反映「好提交必然通过，坏提交可能通过也可能失败」这一事实。p 可以简单地用已知的坏提交上的失败次数除以总测试次数来估计：p = failures /total_runs。

在算法启动时，我们还没有任何失败数据来估计 p。解决方案是：首先在已知的最晚提交（必然是坏的）上重复运行测试，直到观察到第一次失败。以这次失败作为初始种子：用 1 / 失败次数 作为 p 的初始估计。随着更多测试结果累积，p 的估计会自动趋于准确。

当某个原本被认为是 good 的提交上首次出现失败时，p 的估计会显著下降，因为分子（失败次数）增加而分母（总运行次数）也相应增加。相应地，概率分布会向前「回溯」，算法会在更早的提交区间内重新搜索。

关键工程参数

在生产环境中部署贝叶斯二分查找时，以下参数值得关注：

初始种子运行次数：在开始搜索前，在最晚提交上运行测试直到首次失败。建议设置超时机制，例如连续通过 5000 次则强制终止并假定 p 极小（可能并非间歇性 bug）。

p 的先验平滑：如果某次失败后 p 的估计剧烈波动，可在贝叶斯更新时对 p 施加 Beta 先验进行平滑，避免单次异常结果主导整个搜索。

信息增益阈值：当某个提交的后验概率超过 0.95（或其他预设阈值），且前一个提交已连续通过足够多次（例如 50 次），可宣布定位完成。

切换开销阈值：通过 ⌊runs÷10⌋ 中的除数控制测试批大小。如果每次切换提交需要重新编译或重启服务，建议将该除数调大（如 20 或 50）以减少切换频率；反之则可调小以更快获取分布更新。

与传统二分查找的关系

当测试完全确定（即 p = 1）时，贝叶斯二分查找的行为与传统二分查找完全一致。因为在这种情况下，任何一次失败都直接排除了所有更早的提交，概率分布瞬间坍缩到单个点。这说明贝叶斯方法是传统方法的一般化推广 —— 后者是前者在确定性条件下的特例。

然而，在处理间歇性 bug 时，贝叶斯方法的的优势是根本性的。它不要求「必须看到失败才能排除一个提交」，而是通过概率推断持续权衡证据的强度。即使连续通过了一百次，只要这些通过的观察结果在统计上与「该提交是坏的」的假设不矛盾，算法就会保留一定的后验概率，不会过早排除。这种稳健性正是定位间歇性 bug 时最需要的特性。

资料来源：本文算法细节参考 Dave Turner 的博客文章《Bayesian bisection》[1]，该文系统阐述了概率模型构建、后验更新与中位数选择策略。

[1] https://davecturner.github.io/2024/11/11/bayesian-bisection.html