While studying computer science, one of the most important concepts that one needs to learn are the searching algorithms. In this article, we are going to quickly go over the major types of searching algorithms available.
While studying Search Algorithms, the first factor we need to look into is whether the list on which we are performing the search is sorted or not. Based on this knowledge, we can decide which algorithm to implement.
Searching in an Unsorted List
If the list is unsorted then one of the simplest and popular method to perform search is the Linear Search Algorithm. This algorithm, although simple, is computationally expensive (Complexity being O(n)).
In Linear search algorithm, we iterate through the list one element at a time and compare the searched element with the current element. If they match, we return success and if they don’t, we compare the next element in the list. Like this, if even after traversing through the entire list, we are unable to find the searched element, then we return failure.
Searching in a Sorted List
When we have a sorted list in our hand, then we can choose from a number of available search algorithms. The most commonly used is the Binary Search Algorithm, which has a worst case time complexity of O(logn).
- Binary Search Algorithm — Binary Search uses the divide and conquer philosophy. With every iteration, we either find the searched element or decrease the searching range by half. For implementing the Binary Search Algorithm, the length of the list or the index of the last element must be known.
In the flowchart, Left and Right denote the index of first and last element in the list respectively. We first check if Left is less than Right. If the condition is satisfied, then we compute the MID position as MID = (Left + Right)/2.
We look for the searched element in the MID position. If it is found, we return success, else we need to check if the searched element is less than the element present in the MID index. If it is true, then we update the “Right” position as Right = MID-1, else, if the searched element is greater than the element present in MID, then we update the “Left” position as Left = MID + 1.
After updating the Left and Right values, the loop is initiated again.
2. Jump Search Algorithm — Jump Search Algorithm can be thought of as a modified linear search where instead of traversing one element at a time we jump “k” number of elements in the list. If the current element is greater than the searched element, then we go back “k” elements and perform a linear search from there.
The above flowchart shows the basic building blocks of the jump search algorithm. However, we do need to keep in mind that we might exceed the list size while jumping and such a case needs to be handled. Complexity wise, the time complexity of Jump search is between that of linear search and binary search.
3. Exponential Search — Exponential search algorithm can be thought of as a modified binary search algorithm. In Binary search algorithm, one needs to apply the algorithm over the entire range of the list. In Exponential Search, the range on which binary search is applied is reduced, making it more efficient.
Let the variable which tracks the index of the current element in the list be “i”, then as long as the current element is less than the searched element, we increase the value of “i” as (i=i*2). Once the value at index “i” is greater than the searched element, we perform a Binary search on the sub-list whose starting index is (i/2) and ending index is i.
There is quite a bit of similarity between the philosophy of Jump Search and Exponential Search Algorithms. For churning out the final output, both of them need to call a secondary search algorithm (Jump search calls Linear Search while Exponential Search calls Binary Search). Worst case time complexity of Exponential Search is O(log(k)). Where k is the index of target element.
4. Interpolation Search — Interpolation Search is a little unique as it can be said to be a “formula based” Algorithm. The formula used for calculating the position to be searched in the list is:
In the above equation, end and start are indexes, l[end] and l[start] represent the element at index end and start respectively and S represents the searched element.
Being a formula based searching technique, this works like a charm for arrays whose elements are uniformly distributed. For example, let us look at the following arrays “arr_A” and “arr_B”.
arr_A = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,14, 15, 16, 17, 18, 19, 20, 21, 22
arr_B = 0, 3, 6, 9, 12, 15, 18, 21, 24, 27,30, 33, 36, 39, 42
In both of the arrays, the elements are uniformly distributed. If we apply the formula on these types of arrays, then we can find the index of the searched element in the first iteration itself.
From the adjacent examples, we can see that the index of the searched element can be calculated using the formula IF the elements in the array are uniformly distributed.
However if uniform distribution is not present, then we have to iteratively search for the required element. This is done in a same manner as we did in Binary Search Algorithm. That is, if the element in the calculated position (pos) is less than the searched element, then we update the value of start as pos+1. Else, if the element in the calculated position is greater than the searched element, then we update the value of end variable as pos-1. With these new updated values, we start the loop again.
The Interpolation Search Algorithm is an improvement on the Binary Search. While the Binary Search splits the list from the middle, the interpolation search uses the calculated position (pos) to perform this action.
The average case complexity of Interpolation Search is O(log (log (n))). However, the worst case time complexity for interpolation search is still O(n). This is because, when the values in the array increase exponentially, then the program has to check every element thus making n number of comparisons.
In this article, we briefly discussed the most common types of Searching Algorithms. Deeply studying these different types of Search Algorithms is a great way to develop programing logic as every search algorithm is unique in its own way.
Deciding which algorithm to implement is largely dependent on the type of array/list on which we would implement our algorithm. Sometimes a simple, computationally expensive algorithm would work just fine while in some other situation we might want to optimize our approach especially if the range is quite large.