 # Linear Search in Data Structures

Amit Kumar Ghosh  33 min read
21 Sep 2023
Intermediate
542 Views

## Linear Search in Data Structure: An Overview

Are you seeking an efficient way to search for something within a data structure? The linear search might be exactly what you're after. Often used in computer science and programming, linear search is a key tool that helps make searching large amounts of data quick and simple. In this article, we'll explore the basics of linear search including what it is, how it works, implementation strategies, and Complexity Analysis of Linear Search. We'll also discuss linear search algorithms, Linear search in data structures with examples, linear search program in data structures, and the traditional methods of employing linear search across diverse datasets.

## What is linear search in data structure? Linear search is a fundamental algorithm in computer science used to locate an element in a list or array. It is a brute force approach where elements are sequentially checked from the beginning to the end until the desired element is found. Although linear search is not the most efficient search algorithm, it remains versatile and useful in many applications. Like seeking a missing object in a cluttered environment, a linear search goes through each thing one by one until it locates the desired item. In programming and data structures, it is an essential tool.

## Linear search algorithm

Linear search, also known as sequential search, is a simple algorithm used to search for a target value within a list or an array. The linear search algorithm sequentially checks each element of the list or array until it finds the target value, or until it has checked every element and determined that the target value is not present. The basic steps of the linear search algorithm are as follows:

• 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.

1. 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.
2. Versatility: Linear search can be applied to a wide range of data structures, including arrays, linked lists, and other types of data structures.
3. Efficiency 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.
4. Memory efficiency: Linear search requires minimal memory, making it a good choice for systems with limited memory resources.
5. 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

1. 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.
2. Limited applicability: Linear search is not well-suited for searching through sorted arrays, as binary search is a more efficient algorithm for this purpose. Linear search is most useful when searching unsorted or small arrays.
3. Inefficient for multiple searches: If you need to perform multiple searches on the same array, the 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.
4. 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.
5. Lack of flexibility: Linear search only works on arrays, which can limit its applicability in certain situations. For example, it cannot be used to search through linked lists or other data structures

## Where is linear searching used?

• Searching an unsorted array or list: When the data is not sorted, linear search is a good choice as it does not require any pre-processing or additional storage.
• Implementing other algorithms: Linear search is often used as a sub-routine in other algorithms, such as bubble sort, selection sort, and insertion sort.
• Debugging: Linear search can be used to debug other algorithms and data structures by verifying the correctness of the output.
• When the size of the data set is small: For small data sets, the time complexity of the linear search is not a concern, and it can be used without any performance issues.

## Linear search using iteration

Iterative implementation of Linear Search is a simple algorithm for finding the position of a target value (usually a number) within an array of elements. It involves iterating through each element of the array until the target value is found, or until all elements have been checked.

### C++

``````// C++ code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1
#include <iostream>
using namespace std;
int search(int arr[], int N, int x)
{
int i;
for (i = 0; i < N; i++)
if (arr[i] == x)
return i;
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 21, 3, 14, 10, 40 };
int x = 10;
int N = sizeof(arr) / sizeof(arr);
// Function call
int result = search(arr, N, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}``````

#### Output

``Element is present at index 3``

#### Explanation

• The program first declares an integer array arr and initializes it with some values.
• It then declares and initializes an integer variable x with the value 10, and an integer variable N with the size of the arr array.
• The program then calls the search() function, passing it the arr, N, and x as arguments.
• The search() function iterates through the arr array using a for loop and checks if each element of the array is equal to x.
• If it finds x, it returns the index at which it was found. If it doesn't find x, it returns -1.
• The return value of the search() function is stored in the integer variable result.
• The program then uses a ternary operator to print either "Element is not present in array" if the result is -1, or "Element is present at index result" if the result is not -1.
• Since x = 10 is present in arr at index 3, the output of the program is "Element is present at index 3".

### Java

``````// Java code for linearly searching x in arr[]. If x
// is present then return its location, otherwise
// return -1
class ScholarHat {
public static int search(int arr[], int x)
{
int N = arr.length;
for (int i = 0; i < N; i++) {
if (arr[i] == x)
return i;
}
return -1;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 21, 3, 14, 10, 40 };
int x = 10;
// Function call
int result = search(arr, x);
if (result == -1)
System.out.print(
"Element is not present in array");
else
System.out.print("Element is present at index "
+ result);
}
}``````

#### Output

``Element is present at index 3``

#### Explanation

• This is a Java code implementation of a linear search algorithm, which searches for a given element in an array by sequentially checking each element of the array until a match is found or the end of the array is reached.
• The main function is used to test the implementation of the search function, which takes an integer array and an integer value x as input parameters.
• The search function returns the index of the first occurrence of x in the array if found, and -1 otherwise.
• The search function works by iterating over each element of the array using a for loop and comparing the current element with the target value x.
• If a match is found, the index of that element is returned.
• Otherwise, if the loop completes without finding a match, -1 is returned.
• In the example code, the integer array arr is initialized with some values, and the integer x is set to 10.
• The search function is called with arr and x as arguments, and the returned value is stored in the variable result.
• If the result is equal to -1, it means that the element was not found in the array, and a corresponding message is printed.
• Otherwise, the index of the element is printed.

### Python

``````# Python3 code to linearly search x in arr[].
# If x is present then return its location,
# otherwise return -1
def search(arr, N, x):
for i in range(0, N):
if (arr[i] == x):
return i
return -1
# Driver Code
if __name__ == "__main__":
arr = [21, 3, 14, 10, 40]
x = 10
N = len(arr)
# Function call
result = search(arr, N, x)
if(result == -1):
print("Element is not present in array")
else:
print("Element is present at index", result)``````

#### Output

``Element is present at index 3``

#### Explanation

• This is a Python code implementation of a linear search algorithm, which searches for a given element in an array by sequentially checking each element of the array until a match is found or the end of the array is reached.
• The search function takes an integer array arr, its length N, and an integer value x as input parameters.
• The function returns the index of the first occurrence of x in the array if found, and -1 otherwise.
• The search function works by iterating over each element of the array using a for loop and comparing the current element with the target value x.
• If a match is found, the index of that element is returned.
• Otherwise, if the loop completes without finding a match, -1 is returned.
• In the example code, the integer array arr is initialized with some values, and the integer x is set to 10.
• The length of the array N is computed using the len function.
• The search function is called with arr, N, and x as arguments, and the returned value is stored in the variable result.
• If the result is equal to -1, it means that the element was not found in the array, and a corresponding message is printed.
• Otherwise, the index of the element is printed

## Linear search using recursion

The recursive approach for linear search involves dividing a list or array of elements into smaller sub-arrays and searching each sub-array recursively until the target element is found or the entire list has been searched.

### C++

``````// C++ Recursive Code For Linear Search
#include <iostream>
using namespace std;
int linearsearch(int arr[], int size, int key)
{
if (size == 0) {
return -1;
}
else if (arr[size - 1] == key) {
// Return the index of found key.
return size - 1;
}
else {
int ans = linearsearch(arr, size - 1, key);
return ans;
}
}
// Driver Code
int main()
{
int arr = { 5, 165, 71, 19, 4 };
int key = 4;
// Function call
int ans = linearsearch(arr, 5, key);
if (ans == -1) {
cout << "The element " << key << " is not found."
<< endl;
}
else {
cout << "The element " << key << " is found at "
<< ans << " index of the given array." << endl;
}
return 0;
}``````

#### Output

``The element 4 is found at 4 index of the given array.``

#### Explanation

• This C++ code implements linear search using a recursive approach.
• Linear search is a simple searching algorithm that checks each element of an array until it finds the desired value or reaches the end of the array.
• The code takes an integer array arr of size and a key value key that needs to be searched in the array.
• The linearsearch() function recursively searches for the key value in the array using the following steps:
• Base case: If the size of the array is zero, it means that the key value is not present in the array, and hence the function returns -1.
• If the last element of the array is equal to the key value, the function returns the index of that element (i.e., size-1).
• Otherwise, the function recursively calls itself with the array size reduced by one (i.e., size-1), until it either finds the key value or reaches the base case.
• The main() function initializes an integer array arr with 5 values and a key value key to search in the array.
• It calls the linearsearch() function and stores its return value in the variable ans.
• If the returned value is -1, the key value is not found in the array, and the program displays a message indicating the same.
• If the returned value is not -1, the program displays a message indicating the index of the key value in the array.
• Finally, the program returns 0 to indicate successful completion.

### Java

``````// Java Recursive Code For Linear Search
import java.io.*;
class Test {
static int arr[] = { 5, 165, 71, 19, 4 };
// Recursive Method to search key in the array
static int linearsearch(int arr[], int size, int key)
{
if (size == 0) {
return -1;
}
else if (arr[size - 1] == key) {
// Return the index of found key.
return size - 1;
}
else {
return linearsearch(arr, size - 1, key);
}
}
// Driver method
public static void main(String[] args)
{
int key = 4;
// Function call to find key
int index = linearsearch(arr, arr.length, key);
if (index != -1)
System.out.println(
"The element " + key + " is found at "
+ index + " index of the given array.");
else
System.out.println("The element " + key
}
}``````

#### Output

``The element 4 is found at 4 index of the given array.``

#### Explanation

• This Java code demonstrates the implementation of linear search using recursion.
• The program initializes an integer array arr with some elements.
• The linearsearch() method is then defined which takes three arguments: an integer array, arr, the size of the array, size, and the key to be searched, key.
• The linearsearch() method recursively searches for the key in the given array.
• If the size of the array becomes 0, it means that the key is not found, and the method returns -1.
• If the key is found at the last element of the array, it returns the index of that element.
• Otherwise, the method calls itself recursively with the size of the array decreased by 1.
• The main() method calls the linearsearch() method with the arr array, its length, and the key to be searched.
• If the returned index is not -1, it prints a message indicating that the key is found at the returned index.
• Otherwise, it prints a message indicating that the key is not found in the array.
• In this particular example, the program searches for the key 4 in the arr array and finds it at the 4th index (0-based indexing).
• Therefore, the program outputs the message: "The element 4 is found at the 4 index of the given array."

### Python

``````# Python Program to Implement Linear Search Recursively
def linear_search(arr, key, size):
# If the array is empty we will return -1
if (size == 0):
return -1
elif (arr[size - 1] == key):
# Return the index of found key.
return size - 1
else:
return linear_search(arr, key, size - 1)
# Driver code
if __name__ == "__main__":
arr = [5, 165, 71, 19, 4]
key = 4
size = len(arr)
# Calling the Function
ans = linear_search(arr, key, size)
if ans != -1:
print("The element", key, "is found at",
ans, "index of the given array.")
else:

#### Output

``The element 4 is found at 4 index of the given array.``

#### Explanation

• This Python program implements linear search recursively.
• Linear search is a simple searching algorithm that searches for an element in a given array by sequentially checking each element until a match is found or the whole array has been searched.
• The function linear_search() takes three arguments: arr (the array to be searched), key (the element to be searched for), and size (the size of the array).
• The program starts by checking if the array is empty (if size == 0).
• If it is empty, the function returns -1, indicating that the element was not found.
• If the array is not empty, the program checks if the last element of the array (arr[size - 1]) is equal to the key.
• If it is, the function returns the index of the found key (size - 1). Otherwise, the function recursively calls itself with the array, the key, and the size decremented by 1.
• In the main program, an array arr is initialized with some elements, and a key to be searched for is also defined.
• The linear_search() function is then called with these parameters.
• If the function returns an index other than -1, it means that the element was found in the array, and the program prints a message with the index where the key was found.
• If the function returns -1, it means that the key was not found in the array, and the program prints a message indicating this.

## The Complexity of Linear Search Algorithm

When using the Linear Search Algorithm, you will run across three different types of difficulties:

• Best Case
• Worst Case
• Average Case

### Best Case Complexity

• In the top spot, the element under search might be discovered.
• In this case, there is just one successful comparison left after the search.
• Thus, the linear search algorithm executes O(1) operations in the best-case situation.

### Worst Case Complexity

• The element that is wanted might not even exist or it might be at the very end of the array.
• The search is successful in the first scenario after 'n' comparisons.
• The search fails after 'n' comparisons in the following scenario.
• Thus, the linear search algorithm executes O(n) operations in the worst-case situation.

### Average Case Complexity

• The average case for the linear search algorithm is O(n) when the element to be searched is in the middle of the array.

## Application of Linear Search Algorithm

• Both single-dimensional & multi-dimensional arrays can be searched linearly.
• When the array just has a few elements, linear search is simple to use and efficient.
• When a single search is being fetched from an unordered list, linear search is still effective.

## Code Implementation of Linear Search Algorithm

``` ```
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Return the index where the target is found
return -1 # Return -1 if the target is not in the array

# Example usage:
my_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
target_value = 6
result = linear_search(my_list, target_value)

if result != -1:
print(f"Target {target_value} found at index {result}.")
else:

```
```
``` ```
public class LinearSearch {
public static int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Return the index where the target is found
}
}
return -1; // Return -1 if the target is not in the array
}

public static void main(String[] args) {
int[] myArray = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int targetValue = 6;
int result = linearSearch(myArray, targetValue);

if (result != -1) {
System.out.println("Target " + targetValue + " found at index " + result + ".");
} else {
}
}
}
``````}
```
```
``` ```
#include <iostream>

int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // Return the index where the target is found
}
}
return -1; // Return -1 if the target is not in the array
}

int main() {
int myArray[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int targetValue = 6;
int size = sizeof(myArray) / sizeof(myArray);
int result = linearSearch(myArray, size, targetValue);

if (result != -1) {
std::cout << "Target " << targetValue << " found at index " << result << "." << std::endl;
} else {
std::cout << "Target " << targetValue << " not found in the array." << std::endl;
}

return 0;
}
```
```

In this example, the target value (6) in the myArray is located using a linear search, and the outcome is then printed. In this instance, the target value (6) in the myArray was located at index 7.

#### Output

``Target 6 found at index 7.``

## FAQs

### 1. What is linear search in data structure?

A simple procedure for finding a given element in a list, linear search in data structures sequentially checks each element until a match is discovered or the list's end is reached.

### 2. What are the 4 types of linear data structure?

Arrays, linked lists, stacks, & queues are the four various types of linear data structures.

### 3. What are linear search advantages in data structure?

The advantages of linear search include its simplicity and suitability for use with unsorted data.

### 4. What is linear search used for?

To locate a specific element in a list or array, use linear search.

### 5. Where is linear search used?

In situations when data is not sorted or when simplicity is preferred over performance, such as with small datasets or as a fundamental building element for more complex algorithms, linear search is frequently used.

##### Summary

By understanding the concept of linear search in data structures, we can become better equipped to find and manipulate data quickly and effectively. Linear search is a simple yet powerful tool for finding specific elements in an array or list. It’s important to understand the basics of how it works in order to ensure optimal performance when dealing with large datasets. In computer science, linear search is a fundamental concept. As the foundation for more complex algorithms, it is important to comprehend in order to develop one's knowledge of the subject.

Similar Articles 