Internship Assurance

DevOps & Cloud Engineering

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.

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.

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**

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.

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.

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.

**Output**

**Example 2: **The example below searches for the index 9 in the given array if it is present.

**Program**

**Output**

**Example 3: **This example searches the index of 2 in the given array if it is present.

**Program**

**Output**

Internship Assurance

DevOps & Cloud Engineering

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.

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.

Book a free counselling session

Get a personalized career roadmap

Get tailored program recommendations

Explore industry trends and job opportunities

Programs tailored for your success

Popular

Data Science

Technology

Finance

Management

Future Tech

Upskill with expert articles

View all

Hero Vired is a leading LearnTech company dedicated to offering cutting-edge programs in collaboration with top-tier global institutions. As part of the esteemed Hero Group, we are committed to revolutionizing the skill development landscape in India. Our programs, delivered by industry experts, are designed to empower professionals and students with the skills they need to thrive in today’s competitive job market.

Privacy policy and Terms of use

© 2024 Hero Vired. All rights reserved