What is the Linear Search Algorithm
Last week, we described binary search in Python. In this tutorial, we’re going to do the same thing with a new search algorithm: the linear search algorithm.
The linear search algorithm is one of the simplest search algorithms. The input to a linear search algorithm is an array or list and an item. The algorithm searches for the presence of the item inside the array. If the item is found, the index of the item is returned. Otherwise, it can return null or any other value that you think can’t exist inside the array.
Here are the basic steps for performing a the linear search algorithm in Python:
- Search the input item at the first index (0 index) of the array.
- Check if the item is found at the current index. If yes, return the index and move to step 5.
- Check if the current index is the last index of the array. If yes, return null and move to step 5.
- Move to the next index in the array and go to step 2.
- Stop the algorithm.
Dry Run the Linear Search algorithm
Before we implement the linear search algorithm in Python, let’s try to step through the logic of the linear search algorithm using an example.
Suppose we have a list of integers and we want to search for the integer 15 inside the list. Your Python setup might look something like this:
nums = [4,9,15,21,25,28,35,38,40,45]
item = 15
Iteration 1
Step 1: Search the item 15 at the 0th index of the
Step 2: Check if 15 exists at the current index (index 0). This will not return true since the current index contains the item 4. So we move to step 3.
Step 3: Check if the current index is the last index of the
Step 4: Move to index 1 of the
Iteration 2
Step 2: Check if 15 exists at the current index (index 1). This will not return true since the current index contains the item 9. So we move to step 3.
Step 3: Check if the current index is the last index of the
Step 4: Move to index 2 of the
Iteration 3
Step 2: Check if 15 exists at the current index (index 2). This will return true since the current index contains the item 15. The index 2 will be returned to the calling function and we move to step 5.
Step 5: Stop the algorithm.
Code More, Distract Less: Support Our Ad-Free Site
You might have noticed we removed ads from our site - we hope this enhances your learning experience. To help sustain this, please take a look at our Python Developer Kit and our comprehensive cheat sheets. Each purchase directly supports this site, ensuring we can continue to offer you quality, distraction-free tutorials.
Implementation of the Linear Search Algorithm in Python
Since the logic of the linear search algorithm is really simple, the implementation of the linear search algorithm in Python is likewise simple. We create a for loop that iterates through the input array. If the item is found at any index of the array, that array index is printed and we can break the for loop. Otherwise, if the for loop ends and the item is not found, we can print that the item is not found.
Here is a non-function implementation of the linear search algorithm in Python.
nums = [4,9,15,21,25,28,35,38,40,45]
item = 38
value_found = False
for i in range(len(nums)):
if nums[i] == item:
value_found = True
print("Item found at index ", i)
break
if value_found == False:
print("Item not found")
Output:
Item found at index 7
And here is a function implementation of the linear search algorithm. The function lin_search()
in the following script accepts an input array and the item to be searched as its parameters.
Inside the function a for loop iterates through all the items of the input array. If the item is found at any index, the index value is returned. Otherwise, the Null value is returned.
def lin_search(nums, item):
for i in range(len(nums)):
if nums[i] == item:
value_found = True
return i
return None
nums = [4,9,15,21,25,28,35,38,40,45]
item = 40
index = lin_search(nums, item)
if index != None:
print("Item found at index", index)
else:
print("Item not found")
Output:
Item found at index 8
The time complexity of the linear search algorithm is N where N is the number of items in the input array. This is the case where the item is found at the last index of the input array after iterating through all the array items.
Clearly, the linear search algorithm isn’t the most efficient way to find an element’s position in a list, but learning how to program the logic of a linear search still remains a useful skill in Python or any other programming language. If you found this helpful and want a few more Python programming examples, enter your email address below.