The Fastest Searching Algorithm: Binary Search in Ruby

I am going to start off by saying that this is the fastest searching algorithm with a few caveats. For starters, the data structure that is being search through needs to be sorted. Also, there are some nuances regarding some other algorithms that may search quicker depending on how evenly distributed the sorted data is. But for the most part, if you are looking for an element in a data structure (such as an array) that is already known to be sorted, it is tough to do better than Binary Search.

To illustrate the concept behind Binary Search, I’ll show a way that you already may be doing this in your daily life away from the computer. Back in the 1990’s I was working as an office temporary worker in New York City. One of the offices that I was sent to one day dealt in serial numbers for particular fabric designs. They were all coded with a 12 digit sequence of numbers. They sat me at a small desk and said that wherever the phone rang, I was to pick it up and write down the serial number that the person on the other end of the line read, then I was to go to a wall of cabinets and see if we already had a file for this serial number. There were twenty cabinets and none of them were labeled. The only thing that I did know was that although the cabinets weren’t labeled, the files were indeed arranged in the order of the serial numbers. So, my first call was…