A couple of days ago I had an interview with a big startup in Boulder. I was really excited about the possibility of working there, because they solve some really hard problems on a daily basis, and because I’ve heard great things about their office culture.
It was just supposed to be a quick interview, but it ended up taking a few hours. First, I met up with the CTO. It all started off innocent enough. We went to a restaurant on Pearl Street for lunch. He asked me about my background and skills, and I asked him about the company. We shared personal stories about the flood last summer. After hearing about the way he treats his workers (like adults), and some of the technical details of what they were working on, I was even more excited about the company. We headed went to a coffee shop for a drink, then went back to the office.
When we got there, he introduced me to the head of the team that the best fit for me if I worked there. The team lead, one of his coworkers and I headed back to the coffee shop. We chatted about Rails, Exercism, TDD, and Ember.js, and life at their company. Pretty soon, the CTO came in again. Seeing that we were still talking, he asked the team lead to take me back and “dig in technically” a little bit.
We went back to the office again, and found a conference room. He asked me to solve FizzBuzz in JavaScript. I fired up JasmineNode and built it with tests the whole way. That went fairly well, I thought. Then he asked me a couple of CSS questions. I answered them, and he said that I answered them better than many of the people he interviews.
Finally, we came to some algorithm questions. Although I’ve learned a lot at gSchool in the last five months, algorithms are something that I haven’t spent as much time on, yet. I’ve only had enough programming context to begin understanding them for the last two of those months. I’ve played around with them as much as I could, solving Linked List, the Luhn Algorithm, Nth Prime Factor, Sum of Squares, and Binary Search Tree. I’ve also had a go at writing the MD5 algorithm. But compared to someone with a four year CS degree, I haven’t had much time to get comfortable with them.
My interviewer drew an array on the board, and asked me how I would find a given element’s position within 23 queries. I thought about it, made a guess that it had to do with bit operators, and finally conceded that I had no idea. My heart sunk. Things were going so well. When I asked for the solution, he told me that it was to use a Binary Search. I got excited, because I had done a Binary Search Tree. But no, this was just plain old Binary Search.
Bitten that I didn’t know how to do Binary Search, I set out to build it on my own. This rest of this post is a walkthrough of how I solved it.
Research
First, I visited Wikipedia and read up on Binary Search. It was pretty easy to follow. So easy, in fact, I decided to lift some of the text verbatim and translate it into a set of tests to drive my implementation. Here’s what I found:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 

I decided to take this stepbystep description and turn each step into a test.
Setting Up the Binary Search Test & Class
The first step was to create an object that knew about “an array sorted by key value”, or as I like to call it, a list. I wrote a test:
1 2 3 4 5 6 7 8 

And a class to make it pass:
1 2 3 4 5 6 7 8 

That was easy! Next, it needed to be able to check whether the list was actually sorted, so I wrote a test to make sure it would throw an error if it wasn’t:
1 2 3 4 5 

To make it pass, I implemented the following check: compare the input with itself in sorted form. Not that elegant, but it worked:
1 2 3 4 5 6 7 8 9 

According to the Wikipedia article, the algorithm was going to have to find “the key value of the middle element of the array”. So I wrote a test to make sure that it knew where the middle of its list was:
1 2 3 4 

This was fairly trivial to solve:
1 2 3 4 5 6 7 8 9 10 

With the class all set up, I turned my attention to the actual search algorithm itself.
Building the Search Algorithm
The goal was to search for the index of a specific element, so I wrote a test for a method that did that:
1 2 3 4 

Next came the hard part. I took the text from Wikipedia and broke it down into pseudocode:
 Get the search value
 Find the middle element in the list
 Check if they are equal
 If they are equal, return the position of the middle element in the list
 If they are not equal, branch:
If the search key is less than the middle index:
 Cut the list we’re searching in half
 Instantiate a new BinarySearch
 Pass the first half of the list into it
 Call the search method on the new object, with the same search key
 Repeat until the keys are equal
 If they’re never equal, raise “Not Found”
If the search key is more than the middle index:
 Cut the list we’re searching in half
 Instantiate a new BinarySearch
 Pass the second half of the list into it
 Call the search method on the new object, with the same search key
 Repeat until the keys are equal
 If they’re never equal, raise “Not Found”
With this plan in place, I started to build the method. First, I created the method and passed in the search key:
1 2 3 

Then I checked it against the middle element in the list, returning the index if they were equal:
1 2 3 

The next thing on my to do list was to branch for the other two conditions: whether the key was less than or greater than the middle value:
1 2 3 4 5 6 7 8 9 10 

Then I filled in the branches some more of my pseudocode:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 

I filled them in with real code, one step at a time:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 

Seeing some duplication here, I went ahead and refactored:
1 2 3 4 5 6 7 8 9 10 11 12 

Time to run the tests.
1 2 

Fail.
Why? I did some pry
action and discovered that I was getting back the index of the new list’s middle element, not the original list’s middle element. To fix this, I added the current list’s middle to the recursive call. That meant undoing my refactor. I guess I refactored too soon.
1 2 3 4 5 6 7 8 9 10 11 12 

The tests were now passing. Good. Time to try with another example. This time looking for keys on both sides of the middle.
1 2 3 4 

Whoops! stack level too deep
! I forgot to change value of the search on line 3. I was getting an infinite loop when I searched for a bad value. I skipped this test and wrote one for the bad search condition, instead:
1 2 3 4 5 

To make this pass, I had to validate that the search wasn’t stuck looking through the same sublist over and over:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 

It passed! I went back and rewrote the other test:
1 2 3 4 5 

Passed again! How about one more for good measure? I also wanted to check if the middle was still coming out right when I passed in a list with an even number of elements. All the others had been of an odd length.
1 2 3 4 5 

Ok! Green!
Conclusion
Even if I didn’t know my stuff in the conference room at that moment, I’m glad that my interviewer asked me about Binary Search. It was fun to learn, and it turned out to be a little easier than I expected. I always expect algorithms to be really hard to grasp, but maybe now that I’ve done a few algorithms that use recursion, it’s not such a jump for me to understand it.
At any rate, it’s pretty cool to be able to find an element in a list with so few queries. Lately, I’ve really been enjoying pure math programming problems like this one. I’m going to try to find a few more like this to do in the near future.
Footnote
Since I had already done all of the work, I went ahead and submitted this as a new exercise for Exercism.io. So, if you use Exercism, and you enjoy doing algorithms, I’d suggest giving Binary Search a go yourself. If you get stuck, you know where to find the answer!