09

Nov# What is Linear Search in Data Structures - Its Algorithm, Working, & Complexity

06 Jun 2024

Intermediate

9.08K Views

15 min read

## Linear Search in Data Structures: An Overview

In the previous tutorial,**Searching in Data Structures**, we saw the importance of search operations in computer programming.In this

**DSA tutorial**, we are going to look in detail at one of the most basic searching algorithms,

**Linear Search**. We will learn its features, working, implementation, etc.

To further enhance your understanding and application of linear search concepts, consider enrolling in the best **Best Dsa Course**, where you can gain comprehensive insights into effective **data structure** utilization for improved problem-solving and time management.

## What is Linear Search in Data Structures?

Linear search is a**brute-force**approach where elements in the

**list**or

**array**are sequentially checked from the beginning to the end until the desired element is found. The algorithm compares each element with the target value until a match is found or the entire list has been traversed. If the target value is found, it returns the index of the matching element else it returns a special value, such as -1, to indicate that the value was not found. It is widely used to search an element from the unordered list, i.e., the list in which items are not sorted.

### Linear Search Algorithm

```
LinearSearch(array, key)
for each item in the array
if item == key
return its index
```

**According to the algorithm,**

- Start at the first element of the list or array.
- Compare the target value with the current element.
- If the target value matches the current element, return the index of the current element and terminate the search.
- If the target value does not match the current element, move to the next element in the list or array.
- Repeat steps 2-4 until the target value is found or until every element has been checked.

### Working of Linear Search Algorithm in Data Structures

Let's suppose we need to find element 6 in the given array or list. We will work according to the above-given algorithm.- Start from the first element, and compare the
`key=6`

with each element`x`

. - If
`x == key`

, return the index. - Else, return not found.

**Read More - Best Data Structure Interview Questions and Answers**

## Implementation of Linear Search Algorithm in Different Programming Languages

```
def search(array, key):
# Going through the array sequentially
for i in range(len(array)):
if array[i] == key:
return i
return -1
array = [3, 8, 12, 6, 10, 2]
key = 6
print("The array to be searched is:", end=" ")
for value in array:
print(value, end=",\t")
print()
print("The element to be searched:", key)
result = search(array, key)
if result == -1:
print("Element not found")
else:
print("Element found at index:", result)
```

```
public class LinearSearch {
public static int search(int[] array, int key) {
// Going through the array sequentially
for (int i = 0; i < array.length; i++)
if (array[i] == key)
return i;
return -1;
}
public static void main(String[] args) {
int[] array = {3, 8, 12, 6, 10, 2};
int key = 6;
System.out.print("The array to be searched is: ");
for (int value : array) {
System.out.print(value + ",\t");
}
System.out.println();
System.out.println("The element to be searched: " + key);
int result = search(array, key);
if (result == -1) {
System.out.println("Element not found");
} else {
System.out.println("Element found at index: " + result);
}
}
}
```

```
#include <iostream>
using namespace std;
int search(int array[], int n, int key) {
// Going through the array sequentially
for (int i = 0; i < n; i++)
if (array[i] == key)
return i;
return -1;
}
int main() {
int array[] = {3, 8, 12, 6, 10, 2};
int n = sizeof(array) / sizeof(array[0]);
cout<< "The array to be searched is ";
for (int i = 0; i < n; i++)
cout << array[i] << "," << "\t";
cout << endl;
int key = 6;
cout << "The element to be searched: " << key << endl;
int result = search(array, n, key);
(result == -1) ? cout << "Element not found" : cout << "Element found at index: " << result;
}
```

#### Output

```
The array to be searched is 3, 8, 12, 6, 10, 2,
The element to be searched: 6
Element found at index: 3
```

## Complexity Analysis of Linear Search Algorithm

**Time Complexity****Case****Time Complexity****Best Case**O(1) **Average Case**O(n) **Worst Case**O(n) **Space Complexity:**As we are not using any significant extra memory in linear search, the space complexity is constant, i.e.`O(1)`

.

## When to use Linear Search?

**Small Data Sets:**Linear search works well with small data sets where the number of elements is relatively low.**Unsorted Data:**Linear search is effective when the data is unsorted or the order of elements is not important. It sequentially checks each element until a match is found, regardless of the arrangement of elements.**Singly Linked Lists:**Linear search is commonly used in**singly linked lists**where direct access to elements is not possible. It traverses the list one node at a time, making it a suitable choice for searching through linked structures.**Infrequent Searches:**If searches are infrequent or the list is not frequently updated, linear search can be a straightforward and sufficient solution. It requires minimal setup and is easy to implement.**Educational Purposes:**Linear search is often used as an introductory algorithm in programming and computer science courses to illustrate basic search concepts before moving on to more advanced algorithms.

## Advantages of Linear Search

**Simplicity:**Linear search is a simple algorithm to understand and implement, making it easy to write and debug. It is an ideal algorithm to use when the list of items to be searched is small.**Efficient for small data sets:**For small data sets, linear search can be more efficient than other search algorithms, such as**binary search**, due to the overhead associated with those algorithms.**Memory efficiency:**Linear search requires minimal memory, making it a good choice for systems with limited memory resources.**Flexibility:**Linear search can be used for unsorted lists, which makes it a useful algorithm for cases when the data is not sorted or when sorting the data is expensive or impossible.

## Disadvantages of Linear Search

**Time complexity:**The worst-case time complexity of linear search is`O(n)`

, where n is the size of the array. This means that in the worst-case scenario, the linear search may have to check every element in the array, resulting in a time-consuming search operation. This makes linear search inefficient for large arrays, as the search time increases linearly with the size of the array.**Limited applicability:**Linear search is not well-suited for searching sorted arrays, as**binary search**is a more efficient algorithm for this purpose.**Inefficient for multiple searches:**If you need to perform multiple searches on the same array, a linear search can be inefficient, as it has to search the entire array every time. In contrast, other search algorithms like`binary search`

can take advantage of a pre-sorted array to speed up subsequent searches.**Space complexity:**Linear search has a space complexity of`O(1)`

, meaning it requires a constant amount of memory to perform the search. However, this can be a disadvantage if the array is very large, as it may not fit in memory.

##### Summary

So, here we saw every aspect of the linear search algorithm in data structures. It must not have been difficult to understand as it's the easiest searching algorithm. Just make sure you are thorough with arrays and**linked lists**in data structures. To apply your knowledge of linear search algorithm, enroll in our

**Best Data Structures And Algorithms Course.**

## FAQs

O(1) is the Best Case time complexity of Linear Search Algorithm

The algorithm compares each element of an array with the target value until a match is found or the entire list has been traversed. If the target value is found, it returns the index of the matching element else it returns a special value, such as -1, to indicate that the value was not found.

Linear search is not well-suited for searching sorted arrays, as

**binary search**is a more efficient algorithm for this purpose.