If you ever looked up something in a phone book or dictionary made of paper, you probably used binary search. Open to the middle, check which direction you need to go. Split that half in the middle. Repeat until success. It’s faster than a page-by-page linear search that starts at A.
If you ever played 20 Questions, you also used binary search. The same process, only with all possible things. Is it bigger than a breadbox? Does it exist within a mile of me? Is it inside this house? Good questions can find 220, or about a million choices. Only noobs start with “Is it my uncle’s left eyebrow?” That should be question #20.
Last week, our staff found a minor bug in the new accounting software that took a full day to fix. We probably should have used binary search to solve it, but we didn’t. The Reconcile command sometimes showed the wrong name for transfers between bank accounts. Debugging started at the table display and worked backwards. It was step by step all the way to bad data in the file. The conversion from Goldenseal 4.9x skipped a value. We must have run the code 50 times to discover it.
Linear search does have its good points. You start at one end and keep going. No need for fancy splitting. No risk of accidentally missing something. People don’t use pure binary search on phone books or dictionaries. After getting down to a few pages, it’s easier to stop splitting and just go 1-2-3.
Goldenseal is built with a database library that once used pure binary trees, as on the left:
We changed it to eight branches per node (right image), and everything ran faster. Turns out that a mix of binary and linear search works best. Later, we upped it to 32 branches at each node. That was even faster.
The new accounting app uses very broad trees: up to 1024 branches per node. They’re more like creeping shrubs or ground covers. Wide trees are speedy, but they waste space. Right now an empty file starts at 12 megabytes. We may tweak that design before final release.
Dennis Kolva
Programming Director
TurtleSoft.com
