Searching algorithms are used to check whether an element exists in the given data structure or not. And likewise, if it is found then relevant operation would be performed on it.
Based on the traversing mechanism, it can be classified into two categories. Linear Search and Binary Search.
Linear Search iterates over elements sequentially to find data stored in the given list, whereas, Binary Search randomly compares the middle element of a list with desired data on each iteration and uses divide and conquer approach.
Basis | Linear Search | Binary Search |
---|---|---|
Algorithm | It sequentially searches an element by comparing each element stored in the given list from start to end | It is based on divide and conquer rule. It searches position of a target value within a sorted array |
Sorted List | It is not mandatory to have a sorted list | It is mandatory to have a list to be sorted |
Working | The algorithm works by checking each and every element sequentially at a time until a match is found | The algorithm works by slicing a sorted list into two halves from the middle on each iteration until position of a target value is found |
Implementation | It can implemented on data structures which allow traversal atleast in one way such as arrays and Linked list | It can be implemented on data structures that supports two way traversal only |
Simplicity and Complexity | Simpler and less complex than Binary search | More complex than Linear search |
Approach | It follows sequential approach and is iterative in nature | It follows Divide and Conquer rule |
Time Complexity | The time complexity for Linear search is O(n) | The time complexity for Binary search is O(log n) |
Efficiency | It is not efficient when it comes to search in large data set | It is efficient as compared to Linear Search |
Best Case | The best case occurs when a matching element is found at first position of an array | The best case occurs when a matching element is found at first split which is the middle element of an array |
Also Known | It is also known as Sequential Search | It is also known as half-interval search and logarithmic search |
Linear search, also refereed as Sequential search is a simple technique to search an element in a list or data structure.
It works by sequentially comparing desired element with other elements stored in the given list, until a match is found. In simple other words, it searches an element by iterating over items one by one from start to end.
It is one of the simplest technique to search an element, but also costly and slower when it comes to work with a large datasets.
Further, it is considered to be practical when element list size is small or performing a single search on unsorted list. It is not efficient as Binary Search.
– An algorithm that sequentially searches an element in the given list, without skipping any item
– It follows sequential approach to find an element
– It applies on sequence containers ( that can be accessed sequentially ) such as array,deque, linked list and vector
– It is not mandatory to have an ordered element list, therefore, it is easy to use
– In linear search, performance is calculated using equality comparisons
– O(n) is the worst case scenario in linear search which happens when a searching element is the last element in the list
– O(1) is the best case scenario in linear search which happens when a searching element is matched at very first comparison in the list
– O(n) (n represents number of elements in input range) is the time complexity of linear search.
It is a more efficient method than Linear search and one of the popular ones for searching an element stored in a data structure.
It is mandatory to a list to be sorted.
Based on divide and conquer mechanism, it slices a list into two halves by dividing it from the middle on each iteration.
The middle item is then compared with the searching element if it is greater than the current one ( middle element) then the further search would be performed on right sub-array, discarding left one. The same process would be followed again until a match is not found.
The first step is mandatory, List should be sorted,
Now, Slice it from the middle into two sub-array ( In this case, Index 3 is at middle) and compare the element at that position with searching element which is 25
Since, 25 > 15
Therefore, we moved to the right as greater numbers are lying towards the right by Discarding Left ones
– An algorithm that searches an element by comparing middle or target value, calculated by dividing the given sorted list in two halves on each iteration
– It follows divide and conquer rule
– It applies on data structures where two-way traversal is applicable such as array
– It is not mandatory to have an ordered element list, therefore, it is a bit complex
– In linear search, performance is calculated using ordering comparisons
– O(Log n) is the worst case scenario in binary search
– O(1) is the best case scenario in binary search which happens when a searching element is matched at very first middle element in the list
– O(log n) (n represents number of elements in input range) is the time complexity of binary search
C++ Program to implement Linear Search
#include <iostream> using namespace std; int main () { int searchElement, arrList[5] = { 10, 43, 3, 21, 5 }; int flag = 0; cout << "Enter value to search : "; cin >> searchElement; for (int i = 0; i < 5; i++) if (arrList[i] == searchElement) { cout << "\n Element is Found"; flag = 1; break; } if (flag == 0) cout << "Element does not exist!" ; return 0; }
Output:
Enter value to search : 21 Element is Found
C++ program to implement Binary Search –
#include <iostream> using namespace std; int main() { int f,l,mid,n,s,arr[10]; cout<<"enter no. of elements"; cin>>n; for(int c=0;c<n;c++) { cin>>arr[c]; } cout<<"enter value to search"; cin>>s; f = 0; l = n - 1; mid = (f+l)/2; while (f <= l) { if (arr[mid] < s) { f = mid + 1; } else if (arr[mid] == s) { cout<<"element found"; break; } else{ l = mid - 1; } mid = (f + l)/2; } if (f > l) { cout<<"not found" ; } return 0; }
Output:
enter no. of elements : 5 Provide the values : 23 4 54 3 23 enter value to search : 54 element found
This post was last modified on April 25, 2021