Linear Search is a method of searching an element in a list. It is the simplest searching algorithm in which the element is searched in a sequential manner. Each element of the data structure is compared with the key(element to be searched) in a sequential order until the element is found or the last index is visited.
Illustration:
Algorithm:
LinearSearch(list,key)
for each_item in list
if(item==key)
return item_index
return -1
Linear Search Time Complexity:
- Best Case : O(1)
- Average Case : O(n)
- Worst Case : O(n)
Space complexity: O(1)