The Binary Chop

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

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 on the websites you visit 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 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, but there is a better way.

Using 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 comes back then you know the problem is in the half you turned back on. Otherwise, it is in the other half. So, 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 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. It is also a great example of the kind of thinking that goes behind the design of lots of computer programming.

By the way, if serendipity is smiling on you and you do currently have Chrome problems, the way you access the extensions is as follows:

• Click on the three vertical dots at the top right of the browser window
• Click on “more tools”
• Click on “extensions”

You will see that you can turn extensions on and off without uninstalling them simply by sliding the switch in each extension’s box to the left or right.

The binary chop technique is used in lots of ways by computer programs to find specific items in an “array” of items. The method uses a number of the same steps repeated until a solution is found, and is, therefore, an example of that oft-mentioned beast, an “algorithm”.