A simple solution to the sequence search problems is the linear search algorithm, which is also known as a sequential search algorithm. In this article, I will tell you how to create a linear search algorithm with python.
How Linear Search Algorithm Works?
The linear search algorithm iterates through the sequence one item at a time until the specific item is found or all items have been examined. In Python, a target element can be found in a sequence using the in operator:
Also, Read – Proximity Analysis with Python.
if key in theArray :
print( "The key is in the array." )
else :
print( "The key is not in the array." )Code language: PHP (php)Using the in operator makes our code simple and easy to read, but it hides the inner workings. Below, the in operator is implemented as a linear search.
Consider the unsorted 1-D array of integer values ​​shown in the figure above. To determine if the value 31 is in the array, the search begins with the value of the first element. Since the first element does not contain the target value, the next element in sequential order is compared to the value 31. This process is repeated until the element is found in the sixth position.
But, what if the desired item is not in the array? For example, suppose we want to find the value 8 in the example table. The search begins at the first entry as before, but this time each element in the array is compared to the target value. It cannot be determined that the value is not in sequence until the entire array has been traversed, as shown in the figure above.
Finding a Specific Item using Linear Search Algorithm
The function in the figure above implements the linear search algorithm, which results in a Boolean value indicating the success or failure of the search. This is the same operation performed by the in operator.
A count-controlled loop is used to cycle through the sequence in which each element is compared to the target value. If the element is in the sequence, the loop is terminated and True is returned. Otherwise, a full scan is taken and False is returned after the loop ends.
Searching on an Unsorted Sequence:
def linearSearch(theValues, target):
n = len(theValues)
for i in range(n):
# if the target is in the ith element, return True
if theValues[i] == target:
return True
return FalseCode language: PHP (php)To analyze the linear search algorithm for the worst case, we must first determine which conditions constitute the worst case. Remember that the worst-case happens when the algorithm performs the maximum number of steps.
For a linear search, this happens when the target element is not in the sequence and the loop iterates through the entire sequence. Assuming the sequence contains n elements, the linear search has a worst-case time of O(n).
Searching on a Sorted Sequence
A linear search algorithm can also be performed on a sorted sequence, which is a sequence containing values ​​in a specific order. A linear search algorithm on a sorted sequence works in the same way it does for an unsorted sequence, with only one exception. It is possible to terminate the search prematurely when the value is not in the sequence instead of always having to perform a full scan.
def sortedLinearSearch(theValues, item):
n = len(theValues)
for i in range(n):
# if the target is found in ith element, return True
if theValues[i] == item:
return True
# if target is larger than the ith item, it's not in the sequence
elif theValues[i] > item:
return False
return False Code language: PHP (php)So this is how we can implement a linear search with python. It is a part of Data Structures and Algorithms which is one of the most important topics in any field of Programming.
Also, Read – Interactive Maps with Python.
I hope you liked this article on Linear Search Algorithm with Python. Feel free to ask your valuable questions in the comments section below. You can also follow me on Medium to learn every topic of Python and Machine Learning.
