Introduction – Concept of Linear Search in Data Structure
As we have discussed multiple data structures and algorithms, the Linear Search algorithm is one of them. Since searching is an approach to finding the particular
Element from the list. If we get the desired result, our search is successful otherwise unsuccessful.
Linear searching may be done in two ways ordered/sorted linear search and unordered linear search. It will be easy to search for an element in an ordered or sorted list. But typical in unordered linear search.
Linear search is a sequential search approach of traversing an array or linked list and comparing the required element with the list element. Once we get the required element, we come out of the comparison loop. If the required element is not found then it simply returns null. Let’s see the algorithm based on linear search. The Linear search algorithm works in a similar way to search for the meaning of a particular word from the dictionary in a sequential manner, not in random order.
Linear search algorithm
- Step 1 – Read the search element from the user.
- Step 2 – Compare the search element with the first element in the list.
- Step 3 – If both are matched, then display “Given element is found!!!” and terminate the function
- Step 4 – If both are not matched, then compare the search element with the next element in the list.
- Step 5 – Repeat steps 3 and 4 until the search element is compared with the last element in the list.
- Step 6 – If last element in the list also doesn’t match, then display “Null !!!” and terminate the function.
Consider an Example:
Consider the following list of elements and the element to be searched…
|
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
List |
66 |
30 |
17 |
75 |
38 |
12 |
55 |
89 |
Search element 12
Step 1: Search element (12) is compared with first element (66) index 0.
|
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
List |
66 |
30 |
17 |
75 |
38 |
12 |
55 |
89 |
On comparing no match is found, Compare with the next element.
Step 2: Search element (12) is compared with second element (30) index 1.
|
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
List |
66 |
30 |
17 |
75 |
38 |
12 |
55 |
89 |
On comparing no match is found, Compare with the next element.
Step 3: Search element (12) is compared with third element (17) index 2.
|
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
List |
66 |
30 |
17 |
75 |
38 |
12 |
55 |
89 |
On comparing no match found, Compare with next element.
Step 4: Search element (12) is compared with fourth element (75) index 3.
|
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
List |
66 |
30 |
17 |
75 |
38 |
12 |
55 |
89 |
On comparing no match is found, Compare with the next element.
Step 5: Search element (12) is compared with the fifth element (38) index 4.
|
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
List |
66 |
30 |
17 |
75 |
38 |
12 |
55 |
89 |
On comparing no match is found, Compare with the next element.
Step 6: Search element (12) is compared with sixth element (12) index 5.
|
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
List |
66 |
30 |
17 |
75 |
38 |
12 |
55 |
89 |
On comparing the match found, stop the further comparison and display the element found at index 5.
Programming approach for linear search algorithm:
Implementation of Linear search algorithm in
using namespace std;
int linearSearch(int a[], int n, int val)
{
// Going through array linearly
for (int i = 0; i < n; i++)
{
if (a[i] == val)
return i+1;
}
return -1;
}
int main() {
int a[] = {66, 30, 17, 75, 38, 12, 55, 89}; // given array
int val = 12; // value to be searched
int n = sizeof(a) / sizeof(a[0]); // size of array
int res = linearSearch(a, n, val); // Store result
cout<<“The elements of the array are – “;
for (int i = 0; i < n; i++)
cout<<a[i]<<” “;
cout<<“\nElement to be searched is – “<<val;
if (res == -1)
cout<<“\nElement is not present in the array”;
else
cout<<“\nElement is present at “<<res<<” position of array”;
return 0;
}
Complexity of the Linear Search Algorithm
The complexity of an algorithm is measured in terms of Time and Space in three different cases i.e., Best Case, Average case, and Worst Case.
Best Case Time Complexity
The best-case time complexity of the Linear Search Algorithm is O(1), because when we search for an element from the list and if an element is found in the first position then the search ends with a single successful comparison.
Average Case Time Complexity
The average case time complexity of the linear search algorithm is O(n) because when we search for an element that may be present in the middle of the list then it will take more than half of the time to perform a successful comparison.
Worst Case Time Complexity
The worst-case complexity of the linear search is also O(n) because in this when we search for an element it may present in the last of the list or not at all available in the list. It takes n comparison to compare each element and it will not sure whether the element will be found at nth comparison or not.
Space Complexity of Linear Search Algorithm
Since linear search always does a comparison to search for the required element it does not require to have extra space. Thus, the space complexity of the Linear Search algorithm is always O(n) for an array of n elements.
