In this article, We will see an important concept of Data structure i.e., Linear Search that is simplest Searching Algorithm, after going through the whole article you will come to know about Linear Search, How to implement Linear search, Working procedure (Algorithm) and the Time and Space Complexities.
What is Searching ?
Searching is the process of finding the element in the list (Array, linked-list, Stack, heap etc.) by traversing the whole data set. There are many types of searching algorithms in data structures, but in this article we will see Linear search in detail.
What is Linear Search Algorithm ?
Linear Search is a searching technique which works efficiently with the already sorted list. Hence, if we want to work with the linear search, firstly we have to ensure whether it is sorted or not. Linear Search works on traversing or visiting the each element in sequentially manner, it runs until the desired element found.
Working Procedure (Algorithm)
Step 1 : Compare the searching element (key value) with the each element of the List.
Step 2 : If it is equal to the Searching element then it will terminate and send the index of the same.
Step 3 : If the key value does not match by traversing, then return no match found.
Step 4 : It will search until the whole list will traversed.
Linear Search Program in C++
#include<iostream>
using namespace std;
int main()
{
int n;
cout<<"enter size of array: "; cin>>n;
int arr[n], i, num, index;
cout<<"Enter Numbers: "; for(i=0; i>arr[i];
cout<<"\nEnter a Number to Search: "; cin>>num;
for(i=0; i<n; i++)
{
if(arr[i]==num)
{
index = i;
break;
}
}
cout<<"\nFound at Index No."<<index;
cout<<endl;
return 0;
}Time and Space complexity of Linear Search
Time Complexity in Linear Search
- Best Case : O(1)
- Average Case : O(N)
- Worst Case : O(N)
Space Complexity in Binary Search
- Space complexity : O(1)
Advantages of Linear Search
- Linear Search can be used on arrays of any data type.
- It don’t required any type of additional memory
Disadvantages of Linear Search
- Array on which you want to apply algorithm, should be sorted.
- It takes more time to find tbe element than Binary Search.
Hope all your doubt will be Cleared after reading the whole Article Carefully. You can connect with us using the following links :
Important Links
| Join WhatsApp | Click Here |
| Join Telegram | Click Here |
| Join Twitter (X) | Click Here |
| Join Instagram | Click Here |
