Python Program for Linear Search
Last Updated :
28 Aug, 2023
Problem: Given an array arr[] of n elements, write a function to search a given element x in arr[] using Python.
Examples :
Input : arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
x = 110;
Output : 6
Element x is present at index 6
Input : arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
x = 175;
Output : -1
Element x is not present in arr[].
A simple approach is to do a linear search, i.e
- Start from the leftmost element of arr[] and one by one compare x with each element of arr[]
- If x matches with an element, return the index.
- If x doesn’t match with any of the elements, return -1.
Example: 
Python Program for Linear Search Iterative Approach:
Python
def search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
|
Python Program for Linear Search Recursive Approach:
Python
def search(arr, curr_index, key):
if curr_index == -1:
return -1
if arr[curr_index] == key:
return curr_index
return search(arr, curr_index-1, key)
|
The time complexity of the above algorithm is O(n).
Auxiliary Space: O(1) for iterative and O(n) for recursive.
Please refer complete article on Linear Search and Difference Between Recursive and Iterative Algorithms for more details!
Python Program for Linear Search Using re method
This program uses the regular expression module re to search for a given element in a list. The list is first converted to a comma-separated string and the element is searched in the string using regular expression. If the element is found, the index of the element in the list is calculated by counting the number of commas before the match. If the element is not found, a message is displayed.
Algorithm
1.Import the re module
2.Initialize the input list and element to search for
3.Convert the list to a comma-separated string
4.Use regular expression to search for the element in the string
5.If the element is found, calculate the index of the element in the list by counting the number of commas before the match
6.If the element is not found, display a message
7.Output the result
Python3
import re
arr = [10, 20, 80, 30, 60, 50, 110, 100, 130, 170]
x = 110
arr_str = ','.join(str(i) for i in arr)
match = re.search(r'\b{}\b'.format(x), arr_str)
if match:
result = arr_str[:match.start()].count(',')
print(f"Element {x} is present at index {result}")
else:
print(f"Element {x} is not present in the array")
|
Output
Element 110 is present at index 6
Time Complexity:
The time complexity of this program is O(n) because we need to traverse the entire list to convert it to a string and count the number of commas before the match. The search using regular expression can also take some time depending on the length of the string, but it is generally considered to be a fast operation.
Space Complexity:
The space complexity of this program is O(n) because we need to store the entire list as a string in memory. Additionally, the regular expression module uses some memory for its operations. However, since the input size is relatively small in this case, the space complexity is not a major concern.
Please Login to comment...