Linear Search in Data Structures

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.

Advantages of Linear Search

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

Disadvantages of Linear Search

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[0]);
 // 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)

Element is present at index 3

// 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] = { 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;
}

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

// 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
        + " is not found.");
  }
 }

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

# 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:
   print("The element", key, "is not found.")

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

 
 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:
 print(f"Target {target_value} not found in the list.")
 
 
 

 
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 {
 System.out.println("Target " + targetValue + " not found in the array.");
 }
 }
}
}
 
 

 
 #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[0]);
 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. 

Take our free skill tests to evaluate your skill!

In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.

GET TEST NOW