It's funny: if you asked me that right now, I wouldn't be able to do it. That knowledge was in my brain at some point, but it fell out. I can, however, implement a PR quad tree[0] (which is a trie and not a tree) which allows efficient coordinate search of a 2D space since that's what I've been doing most recently. I think that's more impressive, but it's not what you asked for so I fail the interview. :3

0: https://en.wikipedia.org/wiki/Quadtree

For bonus points you can also implement an Octree.

That would be for coordinate search in 3D spaces. :D

It's fun how easy it is to program in higher dimensional spaces and how hard it is to think in them. Mathematical formalism is a superpower!

Yeah, that's how it appears it really works.

That said, the fundamental idea behind bsearch is toddler easy. It's interesting that such an apparently simple algorithm, namely start in the middle, pick left or right depending on the key, and repeat, is so challenging to code correctly.