# Bisection (software engineering)

Bisection is a method used in software development to identify change sets that result in a specific behavior change. It is mostly employed for finding the patch that introduced a bug. Another application area is finding the patch that indirectly fixed a bug.

## Overview

Code bisection has the goal of minimizing the effort to find a specific change set.

It employs a divide and conquer algorithm that depends on having access to the code history which is usually preserved by revision control in a code repository.

## Bisection method

### Code bisection algorithm

Code history has the structure of a directed acyclic graph which can be topologically sorted. This makes it possible to use a divide and conquer search algorithm which:

• splits up the search space of candidate revisions
• tests for the behavior in question
• reduces the search space depending on the test result
• re-iterates the steps above until a range with at most one bisectable patch candidate remains

### Algorithmic complexity

Bisection is in LSPACE having an algorithmic complexity of ${\displaystyle O(\log N)}$ with ${\displaystyle N}$ denoting the number of revisions in the search space, and is similar to a binary search.

### Desirable repository properties

For code bisection it is desirable that each revision in the search space can be built and tested independently.

## Support by revision control systems

Revision control systems like Git or Mercurial directly support[1][2] code bisection.

Other revision control systems like Bazaar or Subversion support it indirectly employing plugins[3] or external scripts.[4]

## References

1. ^ "git-bisect(1)". Kernel.org. 2012-05-09. Retrieved 2017-01-09.
2. ^ "hg". Selenic.com. Retrieved 2017-01-09.
3. ^ "bisect - Find the revision introducing a bug using a binary search — Bazaar 2.8.0dev1 documentation". Doc.bazaar.canonical.com. Retrieved 2017-01-09.
4. ^ "svn-bisect". Metacpan.org. Retrieved 2017-01-09.