The other day we had a problem that was difficult to find. We tried to work out what was wrong by reading the code, and debugging. Frustration. It’s times like these that I chill out and pull out binary search.
In binary search, you systematically half the problem space. It can reasonably quickly help you pinpoint an issue, without you requiring much thought.
Here’s a situation where it came in handy the other day. Our test suite had a failing test. The test however did not fail when run on it’s own. A test run before it was causing the test to fail.
We made a list of tests. There were about 80 of them, and the failure occurred on the 81st.
We ran the first 40 and the problem test. No failure. So we ran the last 40. 1 Failure. Good, we don’t need the first 40 tests to reproduce the failure. We removed the first 40.
So we started with 81 tests and now have 41. We repeated the process and had 21, and so on. Each iteration took less time than the time before. It’s exciting to narrow down the problem from 30 minutes to 10 seconds! The whole process went something like this:
81 tests in 30min.. 41 tests in 15min.. 21 tests in 7.5min.. etc.. DING! 2 tests in 10 seconds
Once we found the culprit test, we continued the search by removing steps of the test. Eventually the problem was so obvious, it was easy to fix.
Binary search can be a handy problem solving tool when normal techniques let you down.