Linear Search In Python
Overview
We explore a Linear Search in Python 3 algorithm to look at search concepts and to implement a very simple search algorithm. We also breakdown and explain the asymptotic run time and space complexities.
In Computer Science search algorithms are a very fundamental part of learning algorithms. Linear Search is valuable because of its simplicity in looking for a value in an unsorted array. Our Linear Search In Python allows us to learn about the algorithm in a very easy and beginner friendly manner.
Introduction
Linear Search In Python is a searching algorithms and is known for being a simple and sequential searching algorithm. Furthermore, Linear Search is one of the two primary search algorithms, the other being a binary search. A linear search has the drawback of having to look through all elements to determine an element does not exist in the collection.
NOTE: Linear Search does not require a sorted array to work.
First, we will first explain how to do a Linear Search using normal sentences and then we will code out and explain the simple program.
Linear Search In Python 3: General Explanation
First, we begin by selecting the first element in the collection.
Next, we compare our value to the target value. If the element’s value matched our target value then we found the right index if not increment the index.
Lastly, Repeat the previous steps until the value is found or no more values exist to look through.
Linear Search In Python 3: Code Example
We can approach solving this with either a recursive solution or an iterative solution. We will show and explain both.
Iterative Approach : Code
# Iterative Linear Search In Python
#
# collection: array to be search
# target_value: value being searched for
#
# Returns index of x in arr if present, else -1
def iterativeLinearSearch (collection, target_value):
target_index = -1
for val in range(0, len(collection)):
if(collection[val] == target_value):
target_index = val
break
return target_indexIf we run the Iterative function with the following simple program.
# Sorted array to be searched
collection = [ 1, 2, 3, 4, 10, 40, 60, 70, 100 ]
target_value = 10
target_index = iterativeLinearSearch(collection, target_value)
if target_index != -1:
print("Target found at index % d" % target_index)
else:
print("Target not found in collection")We obtain the following output:
Target found at index 4Iterative Approach : Code Explained
First, we must create the function definition for our iterative Linear Search.
def iterativeLinearSearch (collection, target_value): Next, we setup our default return value.
target_index = -1Furthermore, we enter out iterative loop. The iterative loop starts at 0 and iterates up to but not include the length of the collection. We store the index or current iteration number inside the variable val
for val in range(0, len(collection)):Next, We compare the current value at the given index to the target_value. If it is a match we set the target_index to the current iteration value and break out of the loop.
if(collection[val] == target_value):
target_index = val
breakLastly, once we hit the end of our function then we return the target_index. At this point the target_index is either the default value or the index of the found value.
return target_indexThe Linear Search In Python via iterative approach is a simple and effective way to implement the algorithm. We will now explore the recursive method and explain it as well.
Recursive Approach : Code
# Recursive Linear Search In Python
#
# collection: array to be search
# index: the current index to search at
# target_value: value being searched for
#
# Returns index of x in arr if present, else -1
def recursiveLinearSearch (collection, index, target_value):
if(index < len(collection)):
if(collection[index] == target_value):
return index
else:
return recursiveLinearSearch(collection, index + 1, target_value)
else:
# We have surpassed our collection length and
# have not found our target_value
return -1If we run the recursive function with the following simple program.
# Sorted array to be searched
collection = [ 1, 2, 3, 4, 10, 40, 60, 70, 100 ]
target_value = 10
target_index = recursiveLinearSearch(collection, 0, target_value)
if target_index != -1:
print("Target found at index % d" % target_index)
else:
print("Target not found in collection")We obtain the following output, similar to the iterative function in our previous Linear Search in Python example.
Target found at index 4Recursive Approach : Code Explained
Firstly, following the same convention as our Linear Search In Python iterative approach we define our function.
def recursiveLinearSearch (collection, 0, target_value): Next, we setup the base case condition check. The base condition will signal we have reached the end of recursion. We have either iterated all elements in the collection and come up empty or we found the index of the target_value.
if(index < len(collection)):Furthermore, if we have not run out of elements we then execute the code inside our for loop and check our current value. If our current value is our target_value then we return the index.
if(collection[index] == target_value):
return indexOn the other hand, if we have not found the target_value at our current index we recurse by calling ourselves and increasing the index to look at by 1. We now hand off the answer to a recursive call to our own function.
else:
return recursiveLinearSearch(collection, index + 1, target_value) Lastly, we finish our base case by returning a -1 if the current index exceeds the amount of elements in the collection.
else:
# We have surpassed our collection length and
# have not found our target_value
return -1The Linear Search In Python via recursive function is a fun and slightly over-complex way of implementing a simple search for elements. The value from this is to understand how recursion can be used to search using linear search algorithm.
Linear Search In Python 3: Run time Analysis
Our Linear Search In Python has been implemented in both an iterative and recursive approach. Although the recursive approach has more overhead, both the iterative and recursive methods have a run time complexity of O(n).
The O(n) comes from the fact we have to iterate through all elements to determine we don’t have the target_value. If we have N elements we are searching through N indices to find out if we have or don’t have the value at a worse case. The best case is O(1) if the value is the first elements but the average or Big O is O(n).
Time Complexity
O(n)
Space Complexity
The space complexity will depend entirely on the implementation. Our implementations are broken down as follows:
Iterative Approach: O(1)
The Iterative function in our Linear Search in Python example does not grow in memory as it only uses the already allocated array memory to find the value. This does not take into account the memory for the collection as it is assumed this has already been put aside to use. The function itself does not consume more than a single stack frame for itself.
Recursive Approach: O(n)
The Recursive function in our Linear Search in Python does grow because every call to itself requires a new stack frame to be setup on the execution stack. Since our search is O(n) we will have at most n function calls.
Linear Search In Python 3: Conclusion
The linear search has a great advantage in terms of simplicity to implement and does not require a sorted collection. While the time complexity for either iterative or recursive styles is the same. The iterative function is more efficient when we measure space complexity. Either way this concept and knowledge is a great addition to any Computer Scientists or Software Engineer’s algorithm arsenal.
