The Binary Chop

A magnifying glasses focused on a series of zeroes and ones

The “binary chop” (or “binary search”) is a very useful computing technique

a hatchet splitting a small log
A binary chop is so-called because each iteration chops the range of possible solutions in two

Suppose that you use Google Chrome as your internet browser and suppose that it has been playing up recently – perhaps appearing very slow at times or freezing altogether. If you try googling for a potential solution, you may see suggestions that you “investigate installed Google extensions”.

Google extensions are small “add-ons” that add functionality to your browser. For instance, you may have an extension that blocks ads while using Chrome. Another one might download images from the website you are viewing.

It may be that one of these extensions is misbehaving and causing problems to Chrome itself.

To test this, the best thing to do is to to turn all the extensions off and see if the problem goes away. If it does, then the problem appears to be with one of the extensions. So,  your next job is to find out which one is misbehaving.

Suppose that you have 20 such extensions. Testing them one at a time (by turning one back on at once) would require up to 20 steps to find the culprit.

However, there is a better way.

A technique called a “binary chop” (or “binary search”) can greatly speed up the process

What you do is turn half of the extensions back on at once.

If the problem is still present then you know the problem is in the half you turned back on. Otherwise, it is in the other half.

Pork chop cut in twoSo, you chop the half that you now know includes the problem into two and just turn on half of this half. Then see if the problem is present or not.

Keep repeating these steps until you have found the culprit.

In our example we had 20 possible culprits, so it takes one step to narrow the range to 10. A second step narrows it down to 5. A third step narrows it down to 3 (at most). A fourth narrows it down to 2 (at most) and a fifth (at most) will isolate the little beggar.

So, a maximum of five steps will achieve what would otherwise have required up to 20 steps (and an average of 10 steps).

This is a very simple and elegant troubleshooting tool.

The method uses a number of the same steps repeated until a solution is found. This is, therefore, an example of that oft-mentioned beast, an “algorithm”.

Image by alvaro_cabrera on Freepik

Image by timolina on Freepik

Image by freepik