A very interesting topic of data structures is “Search”.
Now, let us first understand what you mean by search in non-technical terms. Search simply means to find the particular element or thing. We often search for lost things or unordered things. For example, I cannot find my blue pen on the study table. I searched it everywhere. We all are well known for this term in our daily lives. Now let us explore what it means in technical language.
A searching operation is performed to find or retrieve the element from any data structure provided. Once the needed element is found, it can be operated accordingly. It is an algorithm to find a particular object from the collection of many objects under the defined type.
Searching is further classified into two types based on the search type.
- Sequential search
- Interval search
Sequential Search
As per its name, the provided list or array is traversed sequentially, one by one until the element is found. For example; linear search
Interval Search
This type of algorithm is particularly used in a sorted type of data structure. They are more complex and more efficient than linear search algorithms. They target the divide and conquer policy by dividing the element into two parts and then calculating the middle element of an array. For example; binary search.
We have discussed the basic introduction to the searching algorithm. Now let us explore them in detail
Firstly, we will know what is the difference between linear search and binary search.
Difference between Linear search and Binary search in tabular form
| Linear Search | Binary Search |
| Linear search is an algorithm for searching used to find the element in the list by searching it until it is found. | Binary search is an algorithm for searching used to find the position of a targeted element within the sorted array. |
| Linear search is also called sequential search. | Binary search is also called half-interval search and logarithmic search. |
| It works by scanning one element at a time without skipping to another element. | It works by dividing the array into half and calculating its middle element. |
| Implementation of linear search is easy | Implementation of binary search is complex |
| Linear search has a time complexity of O(N) | Binary search has a time complexity of O(log2n) |
| Linear search can be implemented on single linked list, double linked list, vector | Binary search can be implemented only on data structures that allow two-way traversal. |
| It is not necessary to sort the array before searching any element | It is necessary to sort the array before searching any element |
| The algorithm of linear search is iterative | The algorithm of binary search follows the divide and conquer rule |
| It includes less line of code | It includes more line of codes |
| Works on an equality comparison | Works on ordering comparison |
Now let us understand each of them in detail.
What is Linear Search?
Linear search is the type of search where each element is checked line by line whether it is the desired element or not. The search will not succeed if all the elements in the list or array are checked but none of them is desired. In this scenario, the worst case will be O(n) i.e. the probability to search for the desired element is its equivalent number of comparisons where n is the number of elements present. Whereas the best case will be O(1), the desired element is found in its first place.
As discussed earlier, linear search is a technique to traverse an element in a sequence, hence called sequential search.
To make our concepts more clear, let us consider one example here. Consider an array of size 100. Here best case that the desired element will be found in O(1) and the worst case will be O(100), as there are 100 elements to be compared.
On that basis, we came to know that linear search is very easy and simple to implement. It is practical when the list has finite/ few elements or when the unordered list performs a single search.
What is Binary Search?
Binary search is an algorithm technique where the calculation is done on the middle element of the list. It is extremely efficient and complex to use. One of the advantages of binary search is that it does not scan every element instead of its search for half of the list. Hence, it takes less time to perform the searching operation. One thing to be considered before you start searching is that the array should be in sorted order. As discussed above that this search uses the divide and conquer technique, let us see how exactly it divides.
Here are three cases used in binary search:
Case 1: data < a[mid] then left = mid+1.
Case 2: data > a[mid] then right = mid-1
Case 3: data = a[mid] // element is found
Here a=name of the array, mid= (left+right)/2
Where left is the left side index of the array and right is the right side index of the array.
The best-case scenario of binary search is the same as linear search i.e. O(1). Whereas the worst-case scenario is O(log2n). The application of binary search is time-saving and gives quick access to the element you are searching for.
In this article, we have seen the important concept of searching and their types. We have also discussed their working and efficiency. Hope you got some relatable information from this article.
Author
Shraddha Changune
SVKM’s Institute of Technology, Dhule
