1.
Introduction
2.
How Does the Linear Search Algorithm Work?
2.1.
Python
2.2.
Explanation of the Code
3.
4.
5.
When to Use Linear Search
6.
6.1.
Can linear search be used on linked lists?
6.2.
Is linear search ever preferable over binary search?
6.3.
How does the size of the dataset affect linear search performance?
7.
Conclusion
Last Updated: May 25, 2024
Easy

# Linear Search in Data Structure

Riya Singh
0 upvote

## Introduction

Linear search is a simple search algorithm used to find an element in a list or array. It checks each element one by one until the target element is found or the end of the list is reached. Linear search is also known as sequential search because it sequentially checks each element.

In this article, we will learn how the linear search algorithm works, its implementation, time & space complexity, advantages, drawbacks, and when to use it.

## How Does the Linear Search Algorithm Work?

The linear search algorithm, also known as sequential search, is a method used to find a particular value in a list. It works by starting at the first element of the list & checking each element sequentially until the target value is found or the list ends. The process is simple: compare each item with the value you are searching for. If the item matches, the search ends successfully; if it reaches the end of the list without finding the value, the item is not in the list.

Python Implementation

``````def linear_search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return f"Element found at index {i}"

In this code:

• arr represents the list where you are searching for the element.

• x is the element you are searching for.

• The function iterates through the list, checking each element (arr[i]) to see if it matches x.

• If a match is found, the function returns the index of the element.

• If no match is found by the end of the list, it returns that the element is not found.

Here's an example of implementing linear search in Python to find a specific element in a list:

• Python

### Python

``def linear_search(data, target):    for index, value in enumerate(data):        if value == target:            return f"Target found at index {index}"    return "Target not found"# Example usage:data_list = [5, 3, 7, 1, 9, 8]target_value = 7result = linear_search(data_list, target_value)print(result)``

Output

``Target found at index 2``

### Explanation of the Code

• Function Definition: The function linear_search takes two parameters: data (the list of elements to search through) and target (the element you're looking for).

• Loop through the List: The function uses a for loop to iterate over data. enumerate is used to get both the index and the value of each element in the list.

• Comparison: In each iteration, the current element (value) is compared to target. If they match, the function returns the index of where the target is found.

• Return if Not Found: If the loop completes without finding the target, the function returns a message indicating the target is not found.

• Easy to Implement: This search algorithm is straightforward to code, making it an excellent choice for beginners who are learning about data searching techniques.

• No Sorting Required: Unlike some other search methods, linear search does not require the data to be sorted beforehand. This can be particularly useful when dealing with lists where sorting is not feasible or would be too time-consuming.

• Effective for Small Data Sets: When the dataset is small, linear search can be very efficient, as the difference in performance between it and more complex algorithms is negligible.

• Flexibility: Linear search can be used on virtually any type of data structure that allows sequential access to its elements, such as arrays, linked lists, and more.

• Detects Duplicates Immediately: As it processes each element sequentially, linear search can easily identify if there are duplicates of the target element in the dataset.

• Slower for Large Datasets: Linear search checks each element one at a time, making it inefficient for searching through large datasets. The time it takes to find an element, or to conclude it's not present, grows directly with the size of the dataset.

• Performance Issues: In scenarios where performance is critical, linear search may not be the best choice due to its basic approach of checking every element until a match is found. This can lead to significant delays in large lists.

• Less Efficient with Ordered Data: If the data is already sorted, linear search does not take advantage of this order. Other algorithms like binary search are much faster on sorted data because they can eliminate half of the remaining elements with each comparison.

• Consistent Run Time: Linear search always has a worst-case scenario where it will check every element in the list, even if the target is found early on or if the list is partially sorted. This consistent run time, while predictable, often means unnecessary checks and a longer average search time.

## When to Use Linear Search

• Small Datasets: Linear search performs well when the dataset is small. Its simplicity and direct method mean that the performance hit from its linear time complexity is minimal.

• Real-time Searching: If the data is being updated frequently and needs immediate searching without reorganization, linear search is beneficial because it doesn't require the data to be sorted or pre-processed.

• Single Search Requirement: When you only need to perform a search once on an unsorted list, using a more complex search algorithm may not be worth the additional setup or sorting time, making linear search a straightforward choice.

• Simple Applications: For educational purposes or simple applications where complexity and scalability are not issues, linear search provides a basic and easy-to-understand solution.

• Searching for Unsorted Data: If the list cannot be efficiently sorted due to constraints, or if the order of items must be preserved, linear search remains one of the few algorithms that can be effectively applied.

### Can linear search be used on linked lists?

Yes, linear search can be applied to any data structure that allows sequential access to its elements, including arrays and linked lists. It's particularly useful for linked lists where random access is not possible.

### Is linear search ever preferable over binary search?

Linear search can be preferable over binary search when dealing with very small datasets or in cases where the list is not sorted and cannot be sorted easily. It's also useful when you need to perform only one or a few searches, minimizing the overhead of sorting required for binary search.

### How does the size of the dataset affect linear search performance?

The performance of linear search decreases as the size of the dataset increases. Since it searches each element sequentially, the time to find an element or conclude it is not present grows linearly with the size of the dataset.

## Conclusion

In this article, we have learned about linear search, a straightforward searching technique used in computer science. We've explored how it works, its implementation, and discussed its time and space complexities. We also reviewed the advantages and drawbacks of using linear search, helping you understand when it might be the best choice. Linear search proves to be a beneficial algorithm in scenarios where simplicity and direct access are prioritized over speed, particularly with small datasets or unsorted data.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.