Binary vs. Linear Search and Ruby’s .find Method

I’m currently learning the Ruby programming language, and I was curious what kind of search is used in Ruby’s .find method for arrays. After a bit of searching around the docs, then figured why not find out for myself. I was interested to see what method of searching .find uses, and whether it was the fastest method to search through arrays or not.

To find this out, I wrote Ruby methods for linear search and binary search, implemented them, and tested their benchmarks with different sized arrays.

Here is how I implemented linear search:

Linear Search in Ruby

Here is how I implemented binary search:

Binary Search in Ruby

In order to test the results and compare them with Ruby’s .find method, I first assigned the target I was looking for to a random number and inserted it into an empty array. Then I added random elements between zero and a million into the array. Once the array was defined, I sorted it as binary search only works on sorted arrays.

Now that I have the array to test, I built a method to measure the benchmarks of each search method. To ensure a representative result, I benchmarked the methods 1,000,000 times, averaged them, and printed the results. I made sure to reset the array and reassign new random elements each time the benchmark was measured. Then, I added a loop to increment the number of elements in the array after each benchmark measurement and print out the results for up to 8 elements in an array.

Method to measure benchmarks

I calculated the total user and cpu times as my result using the Benchmark module. Here are my results:

Interestingly, linear search takes the cake until the size of the array gets beyond 5. After an array larger than 5 elements, binary search quickly overtakes linear as far as speed. Ruby’s .find method clearly is using binary search here as the numbers are exactly the same for .find and binary search.

While it is probably not super important to micro-optimize in a high level language such as Ruby, it is thought provoking to see how different methods of searching through an array can be more efficient. Binary search may be a good all-around method to use, but linear search does win in smaller arrays!