[coding] The Subtle Perils of Binary Search

As many of you know (especially if any of you worked with me at Amazon), I consider House to be a role model, especially with regards to professionalism and workplace ediquette.  I'm not even kidding.  Anyway, upon re-watching the series later, it became clear to me that House was supposed to be an unlikeable character.  Who even saw that coming?  Anyway.  The only thing I really didn't like about him, I mean besides the time he chose not to hook up with Cameron, was the time one of the doctors on his team was suffering from a mysterious illness.  They gave him about 20 different medications, and they knew one of them was fighting the infection, however the interactions between all of those drugs was so toxic that he would be dead before they could kill the infection.

As soon as those parameters were established, I waited with bated breath for House to say "well, take him off half of the medications...." But he didn't.  Because House is a fictional character, and the team of writers that make up the shit he says don't know what Binary Search is.

Anyway.

My business partner for this skin care app thinks that people whose first names are longer than 20-ish character deserve to get facials like just everyone else.  As a person who made the customer text box  310 pixels wide, I disagree.  However it probably won't be long until people with long names start forming organizations and bitching about being discriminated against, so I decided to get a jump on the game and create an automatically resizing text view.

Searching stack overflow came up with complete yet buggy implementations that other people wrote.  This post is about one of those bugs.

I normally hate code written by anyone who isn't me, however AutoResizeTextView looked like a lot of work so I just grabbed a sample implementation.  The guy used a linear search, which seemed pretty dumb.  Determining if something is "big enough" should be a classic case for binary search, right?  His shitty code didn't actually work...in fact it caused all of the text to disappear completely, and I never found out why because I ripped that code out and stole some code by a guy who did use binary search.  Now here is where it gets interesting.

The search space for a TextView that automagically shrinks text in order to fit it inside its width (without wrapping) is, obviously, the font size.  For simplicity, we (I'm using 'we' here, because by the end I had to rewrite the entire binary search component) limited the search space to font sizes that are whole numbers.  This is actually fine, since in Android the "font size" is the font pixel size, and so increasing the font by half a pixel is hard to notice.

So, obviously the bounds for the search are going to be the preferred size at the top (because we dont want to increase the size if it already fits) and a "minimum size" that prevents the text from getting too small to read.  What do we use for the test function?  Well, obviously we pre-render the text at the font size we are testing (the "test size").  If the text rendered at the test size is larger than the width of the TextView, then the test size is too large and we branch left (recurse into the smaller half in the binary search).   If the text rendered at the test size is smaller than the width of the TextView, then the test size is too small and we branch right (recurse into the larger half).  Now, in this paragraph, I've just given you all of the details you need to spot the bug.  So if you can figure out what the bug was without reading on, you're smarter than me.

No seriously, stop reading and try it.  You'll have to also solve the zebra puzzle though, because I did that.  If you get both, though, you're smarter than me.

......

Yeah, so, the interesting thing here is the test.  I said that if the size of the text with the test font was less than the width of the text view, then the font size is too small.  However, that is a lie, because we are searching in discrete incrments.  It can't be too small if its the best we can get.  It is possible, obviously, for one font size to cause the text to be significantly shorter than the width of the TextView, and for the next size to cause the text to be longer (in fact the more text you have, the worse this problem will get, making use of any kind of measurement buffer a stupid choice).  In this case, even though the smaller font size causes the text to be "too short" and is therefore "too small" --it is, technically, the exact size.  Because there is no higher size.  Binary search can be tough when your test function doesn't even realize you have the solution.  I've used a similar technique in my dating life.