Web Log of Ross Chapman

Web Log of Ross Chapman

Two tales of Binary Search

I still have lingering rage from two years ago when an interviewer said to me: “I could probably implement this in about 20 minutes.” Seriously crushing words to utter offhand during a facetime code screen for someone who has been programming and building web apps professionally for 3+ years.

The problem was something like find the nearest value to x in the array. I’m so bad at toy algorithm questions since I basically spent those first 3sh years smashing a ton of Rails and Ember into my brain and worked to be productive building more typical business app/e-commerce style UIs. I wasn’t a whiz at data traversal. More like a deep component interface expert. What else would you call it? Suffice to say a simple filter function at 0(n) time would satisfy the requirements. That is lived experience.

But my interviewer pushed me to consider a big fat array. I was stumped, and failing hard in the spotlight. Only 20 minutes. Bro even let me spend some time after the interview coming up with a solution to email later, but that was futile. I didn’t even know how to properly phrase the problem for Google. I got rejected.

What I learned later is that bro was looking for a solution implementing binary search – something any CS grad would know. I didn’t have a CS background. I learned to program on the job and never had to care about that level of performance in the apps I worked on.

To this day, around 6 years into my career, I haven’t had to implement a binary search algorithm to scan over a big data set.

Julia Evans put out a short series of zine pages recently that describe best practices for debugging. And guess who showed up? Binary search! Leaning back at my desk chair I realized that all along I’ve been using binary search in my every day work.

When fixing a bug without a useful stack trace, triangulating the problematic code requires what I used to think as a kind of cludgy technique: step by step, commenting out large parts of the code at the top and/or bottom of suspect files. Like, literally just comment out half the file where you think the buggy code lives. Does the error still throw? If yes, the problem is not in that half. Try commenting out the other half. If no, then keep halving that part of the file. Recursively repeat. This is binary search. Also, did you notice we’re now also talking about recursion, a topic that even senior programmers have trouble with?

“Advanced” CS concepts can show up in our work all the time. Whether it’s UI, backend, databases, ops, throughout all layers of this mushy cake stack. (“Mushy” as in blended, bleeding, fluid, transitional. Not as in gross, unfit, unstable.) We need to begin reconciling with the danger of narrowly defining their employ and weaponizing them in toy code examples for gatekeeping (cough cough interviewing).

When we learn the meaning behind these CS concepts, we may actually discover more creative ways to use them. Or how they are already part of our toolkit. For example, git-bisect!