Searching | Data Structure & Algorithms
What is searching ?
Searching is a process of locating a particular element present in a given set of elements. The element may be a record, a table, or a file. A search algorithm is an algorithm that accepts an argument ‘a’ and tries to find an element whose value is ‘a’. It is possible that the search for a particular element in a set is unsuccessful if that element does not exist. There are number of techniques available for searching.
The most common searching algorithms are:
- Linear search
- Binary search
- Interpolation search
- Ternary search
Linear Search Algorithm
Linear Search Algorithm is the simplest search algorithm. In this search algorithm a sequential search is made over all the items one by one to search for the targeted item. Each item is checked in sequence until the match is found. If the match is found, particular item is returned otherwise the search continues till the end. The time complexity of above algorithm is O(n).
LinearSearch ( Array A, Value x)Step 1: Set i to 1Step 2: if i > n then go to step 7Step 3: if A[i] = x then go to step 6Step 4: Set i to i + 1Step 5: Go to Step 2Step 6: Print Element x Found at index i and go to step 8Step 7: Print element not foundStep 8: Exit
Binary Search Algorithm
Binary Search Algorithm is fast according to run time complexity. This algorithm works on the basis of divide and conquer rule. In this algorithm we have to sort the data collection in ascending order first then search for the targeted item by comparing the middle most item of the collection. If match found, the index of item is returned. If the middle item is greater than the targeted item, the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the sub array reduces to zero. Time complexity of Binary search algorithm is O(logn)
Step 1: Data list must be ordered list in ascending order.Step 2: Probe middle of listStep 3: If target equals list[mid], FOUND.Step 4: If target < list[mid], discard 1/2 of list between list[mid] and list[last].Step 5: If target > list[mid], discard 1/2 of list between list[first] and list[mid].Step 6: Continue searching the shortened list until either the target is found, or there are no elements to probe.
Interpolation Search Algorithm
Interpolation Search Algorithm is an improvement of Binary Search. It works on the probing position of the required item. It works properly in sorted and equally distributed data lists. Runtime complexity of interpolation search algorithm is Ο(log (log n)).
Step 1: Start searching data from middle of the list.Step 2: If it is a match, return the index of the item, and exit.Step 3: If it is not a match, probe position.Step 4: Divide the list using probing formula and find the new middle.Step 5: If data is greater than middle, search in higher sub-list.Step 6: If data is smaller than middle, search in lower sub-list.Step 7: Repeat until match.
To divide the list into two sub lists, we use mid = Lo + ((Hi — Lo) / (A[Hi] — A[Lo])) * (X — A[Lo])
Ternary Search Algorithm
Ternary search is a divide and conquer Algorithm that can be used to find an element in an array. It is similar to binary search where we divide the array into two parts but in this algorithm, we divide the given array into three parts and determine which has the key (searched element). We can divide the array into three parts by taking mid1 and mid2 which can be calculated as shown below. Initially, l and r will be equal to 0 and n-1 respectively, where n is the length of the array. Time complexity of Ternary search algorithm is O(log3 n)
mid1 = l + (r-l)/3
mid2 = r — (r-l)/3
step 1: First, we compare the key with the element at mid1. If found equal, we return mid1.
step 2: If not, then we compare the key with the element at mid2. If found equal, we return mid2.
step 3: If not, then we check whether the key is less than the element at mid1. If yes, then recur to the first part.
step 4: If not, then we check whether the key is greater than the element at mid2. If yes, then recur to the third part.
step 5: If not, then we recur to the second (middle) part.
Which is the best algorithm for searching?
Unfortunately, there is no “best” searching algorithm. Plain and simple. It’s like asking what are the best clothes to wear. It depends on the season, your body nature and multiple other factors!
Selecting the right algorithm for a task can be painful. It takes both time and effort to construct a suitable algorithm. The same applies to search algorithms. An algorithm has to be selected based on your requirement and the resources that you have.
Generalizing, there are two kinds of searching algorithms.
- Linear Search
- Binary search
For instance, you can opt to do a binary search if your data is stored in a sorted array. With a time complexity of O(logN). It is among the fastest searching algorithms. But the pre-requisite of a sorted array might not always be feasible. On the other hand, you will be stuck to doing a linear search if the same array is unsorted.
Evaluate your requirements and build an algorithm that best fits your needs.