Sequential and Binary Searching Algorithms in Ruby
Searching refers to the algorithmic process of finding a specific item from a collection of items. A search enables us to know whether an item exists in a collection of items. The most common search algorithms are sequential search and binary search. This tutorial explains how these search algorithms work and how they can be implemented in Ruby.
- Sequential Search: When data items are stored in an array, the items have a sequential relationship. Each item is stored in a position relative to the storage positions of the other items. The position of a given item is called an index of that item. Considering the indexes are ordered, it is possible for us to look at the items stored in them in a given order. Starting with the first index in the array, to the last index in the array, we move from index to index, while looking at the item stored there to see if it matches the item we are looking for. If we don’t find a matching item, then it's not part of our items stored in the given array. This process is essentially a sequential search. The sequential search is also called a linear search. The code below shows a simple implementation of a sequential search in Ruby.
An assumption of the sequential search is that the items are not ordered in any way. The probability that a given item can be found at any index on the array is the same. If a given item is not stored in a given array, the only way for us to ascertain that is to compare it against every item in that array. For an array with n items, we will need n comparisons to search an item that either is stored at the last index of the array or one that is not stored in the array at all. While we may have fewer comparisons for an item stored at the beginning of the array (near index 0), the worst-case scenario is to have us compare an item against all items stored in an array. Hence, the complexity of a sequential search is typically O(n).
- Binary Search: The binary search tries to solve the shortcoming of having to search against all items in an array in a sequential search. However, the assumption is that our array is ordered. Hence, an item in index 1 should be larger than an item in index 0, an item in index 2 should be larger than an item in index 1 and item in index 3 should be larger than an item in index 2. Instead of starting searching from the first index in an array, the binary search starts searching from the middle index in the array. If the item stored at the middle index is the one we are looking for, our search is done. If the item is not the one we are looking for, we can compare the item against the item stored on the middle index. If the item is larger than the item stored on the middle index, then we can eliminate the middle item and all items stored on indexes lower than the middle item’s index from our further search consideration. Also, if the item is smaller than the item stored on the middle index, then we can eliminate the middle item and all items stored on indexes above the middle item’s index from our further search consideration. Repeating this process will enable us to know whether a given item exists in a given array. The code below shows a simple implementation of a binary search in Ruby.
The binary search essentially uses the divide and conquer strategy. Our search scope is reduced by half on each iteration. The maximum number of comparisons required to search for a given item is log n, where n is the number of items in the array we are searching. Hence, the complexity of a binary search is typically O(log n).
Even though the binary search seems to have a better complexity, we always need to consider whether it's worth to incur the extra cost of sorting. If we can sort once and search many times, then binary search is the way to go. If we will always have to sort our array to be searched frequently, then the sequential search may be a better option.
Searching refers to the algorithmic process of finding a specific item from a collection of items. A search enables us to know whether an item exists in a collection of items. The most common search algorithms are sequential search and binary search. The binary search algorithm is generally thought to be more efficient than the sequential search algorithm.
