by Andrew Vogel on January 30, 2018

Binary search might be the most well-known search algorithm out there. If you went to school for computer science, you've probably heard the fundamentals of binary search hundreds of times. Chances are, you've been asked about binary search while interviewing for a development job - and for good reason. Binary search is a powerful algorithm. Compared to a linear search it performs very well, and the performance benefit is especially noticeable as the data set grows. A few weeks ago, I got the chance to use it in a live application, but it's been a while since I've worked with this algorithm, so I had to brush up on the implementation.

My pair and I were working on a class in one of our client's applications. This class used a lot of finds and other linear search-esque code to check for items in sorted collections. Being the slick Rocketeers we are, we decided to improve performance time with bsearch: Ruby's built-in binary search implementation. It's also important to note that bsearch only works on sorted collections.

statuses = ["Cancelled", "Completed", "Open", "Options", "Shipped"]

statuses.bsearch { |status| status == "Completed" }
=> nil

Immediately, we knew something wasn't right. How does a searching algorithm miss an element? That's impossible, right? We triple checked our spelling - that was correct. We reverted our method to find - and that worked ok. So what gives?

The first thing that we looked at was brushing up on our Binary Search knowledge. According to Wikipedia:

Binary Search is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.

In theory, bsearch takes our array and looks at each of the sub-arrays that the element is most likely to be in.

Let's say we are searching for "Completed" in the following array.

["Cancelled", "Completed", "Open", "Options", "Shipped"]

First iteration: We look at the middle element - "Open" - Middle element is always floor(n / 2). Since "Open" is greater than "Completed", we know to search the low portion of the array. We should now be looking at:

["Cancelled", "Completed"]

Second iteration: Next, we look at the middle element - "Cancelled". Since "Cancelled" is less than "Completed", we know to search the high portion of the array. We should now be looking at:

 ["Completed"]

Third iteration: We look at the middle element, "Completed", which is also our only element.

"Completed" == "Completed" 

Binary search considers three situations when looking for an element: the element is found, the element resides in the high part of the array, or the element resides in the low part of the array. Therefore, the block passed to bsearch should evaluate to one of 3 values: -1, 0, or 1. In our case, -1 means search the low part, 0 means the element is found, and 1 means search the high part. If you use normal comparison operators like ==, !=, >=, <=, <, or >, the values inside the block can only evaluate to 0 or 1.

We need a way to pass in another value, a negative one, which will tell bsearch to look in the lower half. Luckily, we have our handy-dandy spaceship operator, <=>. For those that don't know, the spaceship operator is an easy way to do a three-way-comparison in Ruby.

And those three comparisons are:

• A < B
• A == B
• A > B

The spaceship operator returns the values -1, 0, 1 depending on the left argument, relative to the right argument. So, order IS important when using the spaceship operator. The value being searched for must appear on the left-hand side of the spaceship.

With that in mind, we can fix our block:

statuses = ["Cancelled", "Completed", "Open", "Options", "Shipped"]

statuses.bsearch { |status| "Completed" <=> status }
=> "Completed"

Thanks for reading! I hope you learned something and are able to use bsearch in your own projects.