Technical interviews — binary search

When in doubt, consider binary search in a technical interview. In technical interviews O(n) is king and O(lg(n)) is definitely the holy grail.

The CS50 professor at Harvard famous demonstrated binary search by looking for a name in the yellow page phone book, and discard half of it at a time (a divide and conquer approach) and dramatically throw the half away. Thereby he was able to reduce the problem by half.

There are many ways to test your knowledge of binary search. And chances are doing a direct binary search is not it.

How do we implement binary search? Sounds like a question Google or Facebook would ask. And it may be a bit complex and subtle. The requirement is O(lg(n)) and hence is a very fast algorithm. Unlike other algorithms that may be easy to implement, especially with extra data structure. How about a binary search tree? It’s a great candidate for a quick technical interview. Not only it tests knowledge about binary search, it also tests trees and recursion. Headaches…

It’s important to know that practice makes perfect and with familiarity there will be perfection. After all, google even rejected home brew creator over trees

Let’s still go back to the basics: how to do binary search. First of all, the list of elements must be sorted. Whenever binary search comes up, the. collection of items must be sorted, else we cannot take advantage of binary search. Ideally there’s no repeated items either.