# 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).

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:

 |g|g|g|g|g|b|b|b|
---------------------> 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)
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)
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 <sean.v.775@gmail.com>
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
module.

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:

#!/bin/sh

HERE=$(dirname$(readlink -f $0)) SCREEN_SIZE=${SCREEN_SIZE:-1000x800}
XDISPLAY=${XDISPLAY:-:1} LOG_LEVEL=${LOG_LEVEL:-DEBUG}
LOG_LEVEL=INFO
if [[ -z $PYTHON ]]; then PYTHON=python fi ./scripts/ffibuild CLIENT="urxvt" Xephyr +extension RANDR -screen${SCREEN_SIZE} ${XDISPLAY} -ac & XEPHYR_PID=$!
sleep 0.5
source ~/workspace/virtualenv/qtile-devel/bin/activate
env DISPLAY=${XDISPLAY}${PYTHON} "${HERE}"/../bin/qtile -l${LOG_LEVEL} $@ & QTILE_PID=$!

export DISPLAY=${XDISPLAY} cd ~/workspace/python/qtile sleep 0.5 ./bin/qtile-cmd -o screen -f info EXIT_CODE=$?

kill -9 $QTILE_PID kill$XEPHYR_PID

exit \$EXIT_CODE