Searching-
- Searching is a process of finding a particular element among several given elements.
- The search is said to be successful if the required element is found otherwise the search is unsuccessful.
- Searching Algorithms are a family of algorithms used for the purpose of searching.
Approaches to searching-
The searching of an element in a given array can be done in two ways-
- Linear Search
- Binary Search
In this article, we will discuss about linear search. Learn about Binary Search here.
Linear Search-
- Linear Search is the simplest approach to searching which searches for an element by comparing it with each element of the array one by one.
- When the required element is successfully found, it returns the index of that element in the array, else it returns -1.
- Because linear search traverses the array sequentially to locate the element, it is also known as Sequential Search.
When Linear Search is applied?
Linear Search is applied when-
- No information is given about the array
- The given array is unsorted or the elements are unordered
- The list of data items is smaller
Linear Search Algorithm-
- Consider there is a linear array ‘a’ of size ‘n’ and linear search algorithm is being used to search an element ‘item’ in this linear array.
- If search ends in success, it sets loc to the index of the element otherwise it sets loc to -1.
Linear_Search (a , n , item , loc)
Begin
for i = 0 to (n – 1) by 1 do
if (a[i] = item) then
set loc = i
Exit
endif
endfor
set loc = -1
End
Analysis of Linear Search-
Best case-
- In the best possible case, the element we are searching for may be found at the first position.
- In this case, the search terminates in success with just one comparison.
- Thus, in best case, the linear search takes O(1) operations.
Worst Case-
- In the worst possible case, the element we are searching for may be present at the last position or not present in the array at all.
- In the former case, the search terminates in success with n comparisons and in the later case, the search terminates in failure with n comparisons.
- Thus, in worst case, the linear search takes O(n) operations.
So, we have-
Time ComplexityTime Complexity of Linear Search = O(n) |
where n is the number of elements in the linear array
Efficiency of Linear Search-
- Linear Search is less efficient when compared with other algorithms like Binary Search and Hash tables that allow significantly faster searching.
Example of Linear Search-
Consider we are given the following linear array and we have to search for element 15 in it.
We will compare the element to be searched (element 15) with all the elements of the given linear array one by one until we find the element 15 or all the elements are searched.
Step-01:
We compare element 15 with the 1^{st} element 92. Since, 15 ≠ 92, so required element is not found. So, we move to the next element.
Step-02:
We compare element 15 with the 2^{nd} element 87. Since, 15 ≠ 87, so required element is not found. So, we move to the next element.
Step-03:
We compare element 15 with the 3^{rd} element 53. Since, 15 ≠ 53, so required element is not found. So, we move to the next element.
Step-04:
We compare element 15 with the 4^{th} element 10. Since, 15 ≠ 10, so required element is not found. So, we move to the next element.
Step-05:
We compare element 15 with the 5^{th} element 15. Since, 15 = 15, so required element is found.
Now, we stop the comparison and return index 4 at which the element being searched is present.
Get more notes and other study material of Design and Analysis of Algorithms (DAA).
Watch video lectures by visiting our YouTube channel LearnVidFun.