Linear Search

Linear Search

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:

LS.gif

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)

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)