What is linear search?
Linear search is used to find a particular element in a list or collection of items.
Target element is compared sequentially with each element of a collection until it is found. Otherwise it will traverse through that list until it reaches to the end of the list.
Time and Space Complexity :
- Best Time Complexity: O(1)
- Average Time Complexity: O(n)
- Worst Time Complexity: O(n)
- Best Space Complexity: O(1)
Example:
Consider the following list of 5 numbers: 21, 34, 5, 47, 11 . We need to find whether number 47 is present in the list or not.
As per linear search algorithm, we will check if our target number i.e. 47 is equal to each number in the list, starting from the first number in the list.
In this case, we will get the result when we reach number 47 in the list at index 3 (Zero-based indexing).
Pseudo code for linear search:
LinearSearch(list, target_element):
{
INITIALIZE index = 0
WHILE (index < number of items in the list)
{
IF (list[index] == target element)
{
RETURN index
}
INCREMENT index by 1
}
RETURN -1
}
Furthermore check out the animation here to learn linear search concept in easy way.
So what do you mean by best case for time complexity?
Well, the best scenario would be to have that item in the first position. Therefore, if the item you are searching for is always listed first, you will find your item in an instant, regardless of your list size.
And what about worst case?
In contrast, when the item is present at last position, you need to traverse through entire list containing n items until you reach the end of the list.
This is the most basic searching algorithm and preferred when you have a small number of items in the list. As number of items increase, it affects the time and space complexity badly.
In practical scenarios, we prefer binary search which has better efficiency in terms of time and space complexity.
Let’s Code
To code in any language other than Python, Click here
Python program to implement linear search:
