共计 2084 个字符，预计需要花费 6 分钟才能阅读完成。
大家好，我是 lucifer。明天给大家分享我的日常工作中罕用的 debug 杀器！
二分代码
当我发现一个难以了解和发现的 bug 的时候，我的 终极方法 就是二分代码。
比方先删去文件 a 的一半代码（大概），而后测试问题是否还在。
- 如果问题不在了，那么咱们就找到了出问题的代码。
- 如果问题还在，那么咱们持续应用同样的方法，持续删去文件 a 的一半代码（大概），而后测试问题是否还在。
- 反复上述步骤，直到找到出问题的代码
这个办法在我一时没有思路或者帮忙他人定位问题的时候十分有用。因为这种做法工夫复杂度大抵是 logn，因而只须要短短几次咱们就能够大抵定位到问题代码。相似地，咱们也能够在多个文件中同时进行二分。
二分提交
更多的时候，咱们是在两次公布之间发现了一个 bug。而这两个公布之间是有若干 commit 的，并且 commit 还不少（几十个甚至上百个）。
咱们也能够应用相似的办法。
- 先切换到两次公布之间的两头提交 x（即便得提交 x 绝对于两次公布之间的间隔差最小）。
实际上这个最小间隔差要么是 0，要么是 1
- 验证问题是否存在。如果不存在，咱们不能确定就是这个提交的问题，无妨先标记以后提交 c 为 good。如果存在，无妨标记以后提交 c 为 bad。
- 通过下面的标记，咱们就能够找到最早出现 bad 的那次提交，并且最要害的是复杂度为 logn，其中 n 为咱们须要验证的提交的总次数。显然，这个工作量比一一查看 commit 要快很多。
不了解其中原理？稍后咱们会讲。
Git 中的二分查找
git 的开发者也想到了这一点，因而提供了 bisect 命令来帮忙咱们做下面这个事件。
应用 bisect 进行问题查找次要依赖于上面的三个命令：
- git bisect start
启动一个查找，start 前面能够加上 good 和 bad 的提交点：
git bisect start [rev bad] [rev good]
如果不加 good 和 bad 的提交点，那么 git 将会等到咱们应用 good 和 bad 命令指定对应的提交点后开始进行查找
- git bisect good
用来标记一个提交点是正确的，前面能够加上 rev 来指定某个特定的提交点，如果不加，则默认标记以后的提交点。
- git bisect bad
用来标记一个提交点是蕴含问题的，如果 bad 后能够加上 rev 来指定某个特定的提交点，如果不加，则默认标记以后的提交点。
背地原理
咱们来补后面的坑。为什么通过这样的标记，咱们就能够找到第一个有问题（标记 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]
因而无论咱们检测的版本是 good 还是 bad，咱们都能够将待检测的版本数量变为一半，也就是说咱们能够在 $logn$ 次内找到第一个有问题的版本。
如果你看过我的二分专题，应该晓得这就是我总结的 最左二分。
- 二分专题（上）
- 二分专题（下）
代码
- 语言反对：Python3
Python3 Code:
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 是其中一个很实用的技巧。最简略的二分找 bug 能够通过删除文件内容的形式进行。而如果文件很多，就很不不便了，这个时候咱们能够应用二分提交来实现。
其中的原理其实也很简略，就是一个奢侈的最左二分。如果大家对此不相熟，强烈建议看下文章中提到的二分专题，两万字总结相对让你有所播种。
