The Binary Search Idea for Narrowing Down Problem Space

Binary search algorithm is a search algorithm that finds the position of a target value within a sorted array. It cuts off the target array in half in a pass, so that it has a worst-case performance of O(log n).
Visualization of the binary search algorithm where 7 is the target value(@wikipedia)

We all know that it's an efficient searching algorithm, but the strategy behind it also applies for narrowing down other problem space, for example, finding out when a bug is first introduced in a series of git commits.

Let's say I have a git repo of 8 commits, the first 5 of which are good, but then the 6th commit introduces a bug, so I have a git commit history looks like below:

---------------------> the git commit history

So I know that the first commit is good and the last (8th) commit is bad (these are initial problem space), by leveraging the strategy of binary search, it can quickly find out that the 6th commit is the first bad commit. (Check the 4th element first, then the 6th.)

Well, that's basically how git bisect works, and it's more powerful, it can be run with a script to determine if current commit is good or not, saving time to verify it manually.

Recently, I finally managed to use git bisect to find out a recession bug (#1410) of qtile, which reports that qtile-cmd doesn't work anymore which the HEAD commit (0617235c), but it works with tag v0.14.2.

With those in mind, here are the steps to catch the first bad commit:

  1. Start the bisect session: git bisect start 0617235c v0.14.2

    $ git bisect start 0617235c v0.14.2
    Bisecting: 88 revisions left to test after this (roughly 7 steps)
    [082e4c7248ac40b69dbe94cfdc4de6aecc5f74ba] Fix debian version
  2. Make a judge script(attached at the end) and find out the commit by running git bisect run ./scripts/git-bisect-judge

    It only takes git 6 steps to find the first broken commit, the output is following with qtile logs being removed:

    $ git bisect run ./scripts/git-bisect-judge
    running ./scripts/git-bisect-judge
    Bisecting: 44 revisions left to test after this (roughly 6 steps)
    [fdb3a324aadb0f934080a703d6835a9a7d203720] Delay power renormalization
    running ./scripts/git-bisect-judge
    Bisecting: 21 revisions left to test after this (roughly 5 steps)
    [0262fbc2ca23d27fa33c4903d7e8a9b8c14d42eb] Move around modules
    running ./scripts/git-bisect-judge
    Bisecting: 10 revisions left to test after this (roughly 4 steps)
    [a3ae3c623859b247813fc1876b188c4d40e84df0] Move calls out of the command graph
    running ./scripts/git-bisect-judge
    Bisecting: 5 revisions left to test after this (roughly 3 steps)
    [036dbcb1b7c5c0fff00fbfbb9688597e2d2f188c] Add tests to the command graph
    running ./scripts/git-bisect-judge
    Bisecting: 2 revisions left to test after this (roughly 1 step)
    [9c3c78ca66905b4e11bfd7a155cfe883cbe12ad6] Create new command graph
    running ./scripts/git-bisect-judge
    Bisecting: 0 revisions left to test after this (roughly 0 steps)
    [ed5eefbf3482481c1f0f4c1cb2eb79e571fec835] Use correct type annotations in IPC module
    running ./scripts/git-bisect-judge
    ed5eefbf3482481c1f0f4c1cb2eb79e571fec835 is the first bad commit
    commit ed5eefbf3482481c1f0f4c1cb2eb79e571fec835
    Author: Sean Vig <>
    Date:   Wed Jun 19 22:33:45 2019 -0400
        Use correct type annotations in IPC module
        With python/typeshed#3061 making it into the most recent release of
        mypy, remove the hacks on the type annotations around the marshal
    :040000 040000 d21cc05b503a0f4658647adad3169efbd84eaa16 f80f29304abd86da9299dfaf22f6719698a37e63 M	libqtile
    bisect run success
  3. End the session by running git bisect reset, git will restores your previouse HEAD commit.

The judge script git-bisect-judege is as follows:


HERE=$(dirname $(readlink -f $0))
if [[ -z $PYTHON ]]; then



Xephyr +extension RANDR -screen ${SCREEN_SIZE} ${XDISPLAY} -ac &
sleep 0.5
source ~/workspace/virtualenv/qtile-devel/bin/activate
env DISPLAY=${XDISPLAY} ${PYTHON} "${HERE}"/../bin/qtile -l ${LOG_LEVEL} $@ &

cd ~/workspace/python/qtile
sleep 0.5
./bin/qtile-cmd -o screen -f info

kill -9 $QTILE_PID


See also

comments powered by Disqus