General idea of binary searching

Imagine that you have found a kernel bug, but you have no idea which of the thousand or more patches included in the tree that you are testing might have caused it to appear. In principle, you could revert the patches one by one and test the kernel after reverting each of them, but that would take way too much time. The solution is to use binary searching, also known as bisection.

To explain what it is we first assume that the kernel does not work for you any more after you have applied a series of $n$ patches ($n$ may be of the order of 1000). We also assume that it takes $\Delta t$ minutes on the average to compile and run the kernel on your system after reverting one patch ($\Delta t$ may be of the order of 10). Under these assumptions, if you tried to revert patches one by one and test the kernel each time, you could spend about $\Delta t \cdot n$ minutes worst-case before finding the offending patch. Of course, you might be lucky and the bug might have been introduced by the last patch in the series, but generally this is not very probable. More precisely, if you know nothing about the patches in question, you should assume that each of them is equally likely to have introduced the bug and therefore the probability of the bug being introduced by a specific patch is equal to $1/n$ (hence, the worst case is not very probable either, but that does not improve the situation very much).

Naturally, you can revert $k$ patches out of $n$ and then test the kernel to see whether or not one of these $k$ patches has introduced the bug. Still, the question arises what number $k$ should be equal to. To answer it, let's estimate the maximum expected time needed to find the patch that has introduced the bug under the assumption that $k$ patches are reverted in the first step. For this purpose, let $A(k)$ denote the event that one of the $k$ patches reverted in the first step has introduced the bug and let $B(k)$ denote the event that the bug has been introduced by one of the remaining $n - k$ patches. If $A(k)$ occurs, the time needed to find the buggy patch will not be greater than $T_A(k) = \Delta t \cdot k$ (we need to search a series of $k$ patches and it takes $\Delta t$ minutes to check one patch on the average) and the probability of occurrence of $A(k)$ is $p_A(k) = k/n$. In turn, if $B(k)$ occurs, the time needed to find the buggy patch will not be greater than $T_B(k) = \Delta t \cdot (n - k)$ and the probability of occurrence of $B(k)$ is $p_B(k) = (n - k)/n$. Hence, since $A(k)$ and $B(k)$ are mutually exclusive and one of them must occur, the maximum average time needed to find the buggy patch is given by

$$T(k) = T_A(k) p_A(k) + T_B(k) p_B(k) = \frac{\Delta t}{n}\left[k^2 + (n - k)^2\right]\:.$$

Now, it takes a little algebra to show that $T(k)$ attains minimum for $k = n/2$, so it is most reasonable to revert $n/2$ patches in the first step.

Further, if the kernel still doesn't work after reverting $n/2$ patches from the series, we get the problem that is formally equivalent to the initial one with the number of patches to search reduced by half. Then, we can repeat the above reasoning for $n' = n/2$ and it will turn out that the most reasonable thing we can do is to revert $n'/2$ patches and test the kernel.

On the other hand, if the kernel works after we have reverted $n/2$ patches from the series, we need to reapply some of the reverted patches and test it once again. In that case, however, we still have $n' = n/2$ patches to check and a reasoning analogous to the above one leads to the conclusion that the most reasonable number of patches to reapply before testing the kernel once again is $n'/2$.

Thus we can establish a procedure, referred to as bisection or binary searching, allowing us to reduce the number of patches to check by half in every step. Namely, if the initial number of patches to check is $n$, we revert $n/2$ patches and test the kernel. Next, depending on the result of the previous test, we either revert or reapply $n/4$ patches and test the kernel once again. Subsequently, depending on the result of the previous test, we either revert or reapply $n/8$ patches and test the kernel once again. By repeating this approximately $\log_2 n$ times we can reduce the number of suspicious patches to one and thus find the patch that has introduced the bug. It is not very difficult to observe that the average time needed to find the buggy patch this way is proportional to $\log_2 n$.