Great write up! I cringe whenever I see that blog post; other spatial indexing systems at Uber were and are designed more thoughtfully, and with better performance characteristics.
I am surprised they're scanning each city linearly, even a crude index (such as boxing), or a binary search would greatly improve the lookup time. I guess if the data fits into the cpu cache the order these are scanned doesn't matter so much?