10 Types of Programming Languages Every Coder should Know
Learn about different types of programming languages and how they are implemented in the real world.
8 mins read
In this article, we will learn about the linear search algorithm, also known as sequential search. This algorithm is widely used for straightforward implementation. It starts from one end and goes through each list element until the desired element is found; otherwise, the search continues until the end of the dataset.
What is Linear Search Algorithm?
Linear search is a computer science algorithm for finding elements in a collection. In a linear search algorithm, each collection element is visited sequentially to find the desired element. Linear search is also known as sequential search.
POSTGRADUATE PROGRAM IN
Multi Cloud Architecture & DevOps
Master cloud architecture, DevOps practices, and automation to build scalable, resilient systems.
How to Perform Linear Search in Python?
This section will explain the Linear Search algorithm in proper working functionality.
Suppose a list of elements is given, and let’s say we want to find the 43 in the list of elements.
Data example : [33,44,99,33,43, 23,4,23]
A step-by-step explanation of the example is given below.
Step 1: We search the list’s first element, ‘33’. We must compare ‘33’ with the target value ‘43’. Since ‘33’ is not equal to ‘43’. So, we move to the next element in the list.
Step 2: Next, we examine the second element, ‘44’. We have to compare ‘44’ with ‘43’. Again, ‘44’ does not match ‘43’, so we continue to the third element.
Step 3: The third element in our list is ‘99. We will compare ‘99’ with ‘43’ and once more. They do not match. So, we proceed to the fourth element.
Step 4: The fourth element is ‘33’. We compare ‘33’ with ‘43’. As before, ‘33’ does not match ‘43’. So, we keep searching and move to the fifth element.
Step 5: We have reached the fifth element, ‘43’. We compare this element with our target value ‘43’. This time, we found a match. The value ‘43’ is indeed the element.
Step 6: We have found the target value and concluded our search. The linear search algorithm has successfully located the value ‘43’ at the index ‘4’ in the list.\
Also Read: Python Tutorial for Beginners
Use Cases of Linear Search
Let’s look at some use cases of linear search algorithms:
- We can use linear search when the array size is not too big or constant. It is easier/faster to implement, thus saving development time.
- This algorithm is easy to understand and apply, so it can be used by developers to search for an element over a small array.
Python Linear Search Algorithm
In this section, we will see the Python linear search algorithm in Python. For a better understanding. Let’s look at the algorithm followed by the following code:
- Create the linear search() function.
- Declare the array, array length, and value to be found as three parameters.
- Initialise the for-loop
- Compare the value of the target key value with each element as you iterate.
- Return index if the element is present.
- Otherwise, the return element is absent.
Python Program for Linear Search
Let’s dive deep into the programming part of the Linear Search in Python.
Example 1: The example below is for searching for the index of 6 in the given array if it is present.
def search(a, l, x):
for i in range(l):
if (a[i] == x):
return i
return -1
a = [33, 44,99,33,43,234,23]
print("The given array is ", a)
x = 43
print("Element to be searched is ", x)
l = len(a)
ind = search(a, l, x)
if(ind == -1):
print("Element Not Found")
else:
print("Element is at index ", ind)
Output
The given array is [33, 44, 99, 33, 43, 234, 23]
Element to be searched is 43
Element is at index 4
Example 2: The example below searches for the index 9 in the given array if it is present.
Program
def search(a, l, x):
for i in range(l):
if (a[i] == x):
return i
return -1
a = [12, 43, 34, 45, 23]
print("The given array is ", a)
x = 9
print("Element to be searched is ", x)
l = len(a)
ind = search(a, l, x)
if(ind == -1):
print("Element Not Found")
else:
print("Element is at index ", ind)
Output
The given array is [12, 43, 34, 45, 23]
Element to be searched is 9
Element Not Found
Example 3: This example searches the index of 2 in the given array if it is present.
Program
def search(a, l, x):
for i in range(l):
if (a[i] == x):
return i
return -1
a = [99, 34, 65, 43, 223]
print("The given array is ", a)
x = 43
print("Element to be searched is ", x)
l = len(a)
ind = search(a, l, x)
if(ind == -1):
print("Element Not Found")
else:
print("Element is at index ", ind)
Output
The given array is [99, 34, 65, 43, 223]
Element to be searched is 43
Element is at index 3
82.9%
of professionals don't believe their degree can help them get ahead at work.
Time and Space Complexity
Let’s see the time and space complexity of the linear search algorithm.
Time Complexity
- Best Case: O(1): This is the best case of linear search algorithm because. It finds the first element in the list. In this scenario, the algorithm finds the target on the first comparison.
- Average Case O(n): This is the average case. The target value will be found somewhere in the middle of the list. The algorithm needs to check approximately half of the elements in the list. Leading to a time complexity of O(n/2), which simplifies to O(n).
- Worst Case O(n): The worst case occurs when the target value is either the last element in the list or not present at all. In this case, the algorithm must check all n elements in the list.
Space Complexity
- The linear search algorithm’s space complexity is O(1) because it uses a constant amount of extra space regardless of the size of the input list. The algorithm only requires a few variables (e.g., the index counter and the target value) to operate.
Conclusion
In this article, we learned that linear search in Python is a straightforward method for finding a target value within a list. This simplest algorithm suits small datasets or scenarios where the list is not sorted. However, its linear time complexity is O(n), which may not be the most efficient choice for large datasets compared to algorithms like binary search. Linear search remains a fundamental computer science concept and is a foundational example of basic searching techniques. Understanding the principle can pave the way for grasping more complex algorithms and data structures used in Programming and software development.
FAQs
What is a linear search?
Linear search is a simple searching algorithm that sequentially checks each list element until it finds the target value or reaches the end of the list.
How does linear search work?
Linear search works by iterating through each element in a list and comparing each element with the target value. If the target value is found, it returns the element's index; otherwise, it continues until the end of the list.
When should I use a linear search?
The time complexity of a linear search is O(n), where n is the number of elements in the list. This means the time it takes to search increases linearly with the list's size.
What is the worst-case time complexity for linear search?
The worst-case time complexity for linear search is O(n). which occurs when the target value is the last element in the list or not present at all.
What are the advantages of linear search?
The advantages of linear search include its simplicity and ease of implementation and its ability to work on unsorted lists without requiring additional preprocessing.
Updated on February 17, 2025
Link
