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:
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)
Program for Linear Search
def search(li, n, x):
for i in range(0, n):
if (li[i] == x):
return i
return -1
inp = input("Enter the list:")
inp=inp.split()
li=[]
for i in inp:
li.append(int(i))
x = int(input("Enter the element to be searched: "))
n = len(li)
# Function call
result = search(li, n, x)
if(result == -1):
print("Element is not present in array")
else:
print("Element is present at index", result)