Hacker News Reader

Comment by readyplayernull | Hacker News Reader

Slowly and for the span of many years I've come to realize that binary search is an amazing problem solving tool, specially on systems that are too big and complex to debug.

For example, recently a colleague had a problem with a rendering tool for Figma, of which we don't have the source code. The tool would take too long exporting a specific design. The team mate tried changing things randomly for days to no avail. Each try would take hours and sometimes crashed the browser.

The solution I gave him was to remove half of the elements and check how that affects the exporting time. Then keep repeating for the groups that still failed. In a matter of hours he found the element that caused a seemingly infinite loop.

View on HN

In the networking classes I took, we used binary search to determine where a problem was occurring, but with a slight twist: Each step away from the end device (e.g. workstation, etc.) take two steps upwards in the network. This broadened your scope easily but allowed for very fast refinement of "These are fine, but this is broken".

It shocks me that people don't think to do this more quickly generally (even intuitively).

I recall a story about a private mailing list with ~1000 participants, where someone was leaking all the messages to the public. To quickly catch the responsible subscriber, the admin used binary search and selectively altered the messages by inserting an extra blank character somewhere.

This is where binary search is not necessary. The admin could have just sent out unique messages, by making binary variations at 10 locations in the email (or ternary variations at 7 locations, or quaternary variations at 5 locations, etc.). E.g. choose 10 words, that can be replaced with a synonym, then generate 2^10 = 1024 unique messages to identify the leaker.

In electricity we do the same. Measure continuity at the halfway point to see if the wire is broken on that half. Rinse and repeat.

That's what we did in electronics too. There were kits with electronic circuits (this was back in the day with transistors.. and a bit more), where the teacher would introduce a fault somewhere. What we were taught was to start measuring signals in the middle, and then continue just like a binary search. This became so natural that when I ended up in programming in my first job I automatically did the same when searching for bugs in software. What surprised me was that other people didn't.

In the old days of DHTML when I was in my early teens this was the way I debugged very messy JS scripts (like multi-level menus). Remove some code - see if it still breaks, remove more, and so on.

Reply on news.ycombinator.com