Linear Search or Sequential Search in python | The Linear search or Sequential search is a method to finding an element within a given list or array. Linear search or Sequential search is usually very simple to implement and is practical when the list has only a few elements, or when performing a single search in an unordered list.
Example:-
Array = {50, 90, 30, 70, 60};
Input to Search = 30
Output:- 30 found at Index 2.
Input to Search = 10
Output:- 10 not found.
How Linear Search Works?
In Linear search, finds the index or location of search in the given array. It begins the search by comparing the search key and the first element of the array/list. If the first element is not equal to the search key then it will compare with the next element, and so on until the match is found or the end of the array. If the match is found then it returns its index, else it will reach the end of the array or list which means the search key is not available.
Let us understand it through an example:- Given array = {50, 90, 30, 70, 60};
Assume the search key = 30; Then traverse through the array and compare with each element. The first element of the array is 50, but 50 is not equal to 30 therefore move to the next element. The next element is 90, but it is also not equal to 30 therefore move to the next element. The next element of the array is 30 which is equal to the search key 30 therefore return the index of the current element of the array.
It was the situation where the search key exists in the array, now let us assume when the search key is not available. Assume the search key = 10. Traverse through the array and compare with each element. It won’t match with 50, 90, 30, 70, 60, and finally reached the end of the array. Therefore return -1 which means the search key is not available.
Algorithm in Python
The procedure to find an element in a given array or list through linear search,
a) Take an array and the search key. Assume they are:- array and key
b) Traverse through the array.
c) Compare key with each element.
d) If the match is found then return the position.
e) Else repeat the process until the end of the array.
f) After traversing the array If the match is not found then return -1.
The algorithm for linear or sequential search can be given as,
def linearSearch(arr, key):
for i in range(len(arr)):
if (arr[i] == key):
return i
return -1Time complexity of the above algorithm:- O(n)
- Best-case performance:- O(1). When the search key is present at the first index/position of the array then only one comparison is required.
- Worst-case performance:- O(n). When the search key is present at the last index of the array then it requires N comparison, where N is the size of the array.
Python Program for Linear Search
# Python program for linear search
def linearSearch(arr, key): #user-defined function
for i in range(len(arr)):
if (arr[i] == key):
return i
return -1
arr = [50, 90, 30, 70, 60] #array
key = 70 #search key
index = linearSearch(arr, key) #calling function
# display result
if (index == -1):
print(key, 'not Found.
else:
print(key, 'Found at Index', index)Output:-
70 Found at Index 3
Python Program to Search an Element in a list
Let us demonstrate a Python program to search an element in a list using linear search algorithm.
In the previous program, inputs(array and search key) are hardcoded in the program but in this program, inputs will be provided by the user.
# Python program for linear search
def linearSearch(arr, key): #user-defined function
for i in range(len(arr)):
if (arr[i] == key):
return i
return -1
arr = input('Enter the array of numbers: ')
arr = arr.split()
arr = [int(x) for x in arr] #array
key = int(input('Enter number to search: ')) #search key
index = linearSearch(arr, key) #calling function
# display result
if (index == -1):
print(key, 'not Found.')
else:
print(key, 'Found at Index', index)Output for the different input values:-
Enter the array of numbers: 1 2 3 4 5
Enter number to search: 3
3 Found at Index 2
Enter the array of numbers: 1 2 3 4 5
Enter number to search: 7
7 not Found.
Enter the array of numbers: 9 10 5 40 25 30 12 28
Enter number to search: 25
25 Found at Index 4
Enter the array of numbers: 12 15 4 19 25 48 7
Enter number to search: 50
50 not Found.
Improved Version
We get worst-case performance O(n) because we are comparing array elements only from one side. Instead of one side, if we compare the array elements from both ends i.e. from the front and last then it will reduce the number of iterations. Let us understand it through an example,
Array = {10, 20, 30, 40, 50};
Search key = 40;
In the first iteration, 40 is not equal to 10 (from the left side), and 40 is not equal to 50 (from the right side).
In the second iteration, 40 is not equal to 20 (from the left side), but 40 is equal to 40.
Therefore the search key found at index 3.
The normal approach can find it in 4 iterations, but an improved linear search can find it in only 2 iterations.
Python Program for the above improved linear search,
# Python program for linear search
def linearSearch(arr, key): #user-defined function
n = len(arr)
i = 0
j = n-1
while(i <= n/2):
if(key == arr[i]):
return i
elif(key == arr[j]):
return j
else:
i = i+1
j = j-1
return -1
arr = [50, 90, 30, 70, 60] #array
key = int(input('Enter number to search: ')) #search key
index = linearSearch(arr, key) #calling function
# display result
if (index == -1):
print(key, 'not Found.')
else:
print(key, 'Found at Index', index)Output:-
Enter number to search: 60
60 Found at Index 4
The best-case time complexity is the same as previous:- O(1)
The worst-case time complexity:- O(n/2)
Also See,
- Linear Search Algorithm in DSA
- C Program for Linear Search
- C++ Program for Linear Search
- Java Program for Linear Search
If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!
