大家好，我是 lucifer。今天给大家分享我的日常工作中常用的 debug 杀器！
二分代码
当我发现一个难以理解和发现的 bug 的时候，我的终极办法就是二分代码。
比如先删去文件 a 的一半代码（大约），然后测试问题是否还在。
- 如果问题不在了，那么我们就找到了出问题的代码。
- 如果问题还在，那么我们继续使用同样的办法，继续删去文件 a 的一半代码（大约），然后测试问题是否还在。
- 重复上述步骤，直到找到出问题的代码
二分提交 更多的时候，我们是在两次发布之间发现了一个 bug。而这两个发布之间是有若干 commit 的，并且 commit 还不少（几十个甚至上百个）。
我们也可以使用类似的方法。
- 先切换到两次发布之间的中间提交 x（即使得提交 x 相对于两次发布之间的距离差最小）。
实际上这个最小距离差要么是 0， 要么是 1
- 验证问题是否存在。如果不存在，我们不能确定就是这个提交的问题，不妨先标记当前提交 c 为 good。如果存在，不妨标记当前提交 c 为 bad。
文章图片
- 经过上面的标记，我们就可以找到最早呈现 bad 的那次提交，并且最关键的是复杂度为 logn，其中 n 为我们需要验证的提交的总次数。显然，这个工作量比逐个检查 commit 要快很多。
不理解其中原理？稍后我们会讲。Git 中的二分查找
git 的开发者也想到了这一点，因此提供了 bisect 命令来帮助我们做上面这个事情。
使用 bisect 进行问题查找主要依赖于下面的三个命令：
- git bisect start
git bisect start [rev bad] [rev good]
如果不加 good 和 bad 的提交点，那么 git 将会等到我们使用 good 和 bad 命令指定对应的提交点后开始进行查找
- git bisect good
- git bisect bad
背后原理 我们来补前面的坑。为什么经过这样的标记，我们就可以找到第一个有问题（标记 bad）的提交？并且时间复杂度为 $O(logn)$。
正好力扣有一道原理，我们直接用它来讲吧。
题目地址(278. 第一个错误的版本)
https://leetcode-cn.com/probl...
题目描述
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。 示例 1：输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。示例 2：输入：n = 1, bad = 1
输出：1 提示：1 <= bad <= n <= 231 - 1思路
可以看出，这个过程和我们上面的描述是一样的。并且我们的目标都是找到第一个出错的提交。
需要明确的是：
- 如果一个版本 x 是 good 的，那么 [1, x] 之间的所有提交肯定都是 good 的，因此待检测版本变为 [x+1,n]
- 如果一个版本 x 是 bad 的，那么 [x, n] 之间所有的提交肯定都是 bad 的。由于我们要找到的是第一个有问题的版本，因此待检测版本变为 [1,x-1]
如果你看过我的二分专题，应该知道这就是我总结的最左二分。
- 二分专题（上）
- 二分专题（下）
- 语言支持：Python3
class Solution:
def firstBadVersion(self, n):
l, r = 1, n
while l <= r:
mid = (l + r) // 2
if isBadVersion(mid):
# 收缩
r = mid - 1
else:
l = mid + 1
return l
复杂度分析
- 时间复杂度：$O(logn)$
- 空间复杂度：$O(1)$
【终极找 bug 大法 - 二分】其中的原理其实也很简单，就是一个朴素的最左二分。如果大家对此不熟悉，强烈建议看下文章中提到的二分专题，两万字总结绝对让你有所收获。
