从二分查找说起

二分查找是一种很简单的算法，适用的对象是 已经排序的数组 。一个最简单的二分查找的实现如下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * @param {Array} sortedList 排好序的list
 * @param {number} target 需要检索的值
 * @return {number} 检索到的值的index，未检索到返回-1
 */

function binarySearch(sortedList, target) {
    let left = 0;
    let right = sortedList.length - 1;
    let middle = parseInt((right+left) / 2);
    while(sortedList[middle] !== target && left !== right) {
        if(sortedList[middle] > target) {
            right = middle - 1;
        } else {
            left = middle + 1;
        }

        middle = parseInt((right + left) / 2);
    }
    return sortedList[middle] === target ? middle : -1;
}

一个简单的递归实现如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

/**
* @param {Array} sortedList 排好序的list
* @param {number} target 需要检索的值
* @return {number} 检索到的值的index，未检索到返回-1
*/

function binarySearch(sortedList, target, left = 0, right = sortedList.length-1) {
    const middle = parseInt((right + left) / 2);
    if(sortedList[middle] === target || left === right) {
        return sortedList[middle] === target ? middle : -1;
    }
    if(sortedList[middle] > target) {
        return binarySearch(sortedList, target, left, middle - 1);
    } else {
        return binarySearch(sortedList, target, middle + 1, right);
    }
}

这里是usfca做的一个二分查找的动画演示 https://www.cs.usfca.edu/~galles/visualization/Search.html

git中的二分查找

让我们进行一下思路的迁移，先看一看一条git branch上的commit记录。

其实很容易发现我们的git commit历史其实在某种意义上很像一个 已经排序的数组 ，所以当我们想找出某个有问题的commit时，二分查找很自然的成为了我们首选的搜索算法。

git bisect

git bisect 就是git内置的二分查找工具，具体用法如下。

1
2
3
4

git bisect start # 开始二分查找
git bisect bad [?index] # 标记错误区间右边界 index 可以是commit hash / tag等。如果不传index那么默认会标注HEAD为bad
git bisect good [index] # 标记错误区间左边界
# 最后错误区间为(good, bad]

当确定区间之后，bisect会提示你区间内有多少个commit，并且最多几次查找可以查找完。同时你会被checkout到区间中心的那个commit上。

如果当前的commit仍是坏的commit, 你可以继续使用 git bisect bad 进行标注，git bisect会应用二分法帮你缩小区间并且checkout到区间中心的commit上，这个过程会一直持续直到二分查找结束。而你最后停下来的commit就是那个有问题的commit。

可视化这个过程大致如下

使用 git bisect run来自动标注

git bisect提供了 git bisect run 这条命令可以在某些情况下帮助我们进行自动化标注。

假设在某个commit中我们的测试挂掉了，我们想找出这个commit。我们使用git bisect的思路是在每次查找完后运行测试，根据测试结果去标注good/bad。

1
2

yarn test
git bisect good # or bad 取决于test结果

以上两条命令可以合并成一条命令

1

git bisect run yarn test

git bisect run 后面接受的是一条shell命令，如果这条命令以 exit(-1) 终止， git bisect 会自动把当前commit标记成bad，否则标记成good。

一些有用的tips

  • 在每一次步进的时候，你可以通过 git bisect visualize 来预览当前的commit区间。
  • 你可以通过 git bisect log 来查看自己的每一次good/bad标注。
  • 如果你记录了git bisect log, 你可以通过 git bisect replay [log-file] 来重放你的git bisect操作。

参考资料

Get good with git: bisect

https://git-scm.com/docs/git-bisect