A while back I walked through the basic idea of binary search. Knowing what binary search is, and implementing it however, are very very different things.

I’ve been taking a technical interviewing course, in order to add some sort of method to the madness of my job hunt. Pretty much every day we’re whiteboarding and mock interviewing. Last night I received the following question while I stood at the whiteboard:

Number of Ones
Given a sorted bit array (values of 0, and 1) determine the number of 1’s in the array.

Input: Array of elements with values belong to the set S : { 0, 1 }
Output: Integer
Example
Input: [0, 0, 0, 1, 1, 1] => Output: 3
Input: [0, 0, 0, 0] => Output: 0

Constraints
Time Complexity: O(log n) A linear search is not acceptable for runtime.
Auxiliary Space Complexity: O(1)

So, the naive solution here would be to iterate over the entire array, and keep count of how many ones we encounter (or just use Ruby’s built in count method…). But of course to check every item in the array that would be time of O(n). Linear search runtime isn’t acceptable!!!

Several things made my mind jump to binary search. First off, the array is sorted. Second, the very obvious time complexity of O(log n). And also the entire array is binary. Isn’t that cute.

But just because you know what to do doesn’t mean that it will be easy. I decided in my approach to have a “middle_index” that I was moving around throughout the array, but I forgot to implement a start_index and an end_index to keep track of my new subarrays. GAH!!! I kept trying to make only middle_index work until I ran out of time. When I was told about the additional markers, it felt so so obvious to me, and so much simpler. In fact, when I was walking through my diagram of the problem on a test array, my hands were the natural bounds of the start_index and the end_index. It just didn’t register.

Anyways, today I went back and finished up my ruby method for this problem. I almost forgot to account for the two cases that might drive me into an infinite loop: an array of all 0’s or all 1’s. I think it will take me several more runs of this, but hopefully someday implementing binary search will be fast and breezy.

And here’s my general Ruby implementation of Binary Search.