What Is Linear Search? Algorithm, Working, Complexity & Examples

15 mins read

In today’s data-driven world, the ability to quickly and efficiently locate information is paramount. Whether you're sifting through a small dataset or scouring vast arrays of information, search algorithms are at the heart of these operations. In this article, we'll explore one of the most fundamental search techniques–Linear Search, breaking down its mechanics, applications, and advantages. 

We have provided clear explanations and practical code examples to help you understand and implement linear search algorithms in your projects.

What Is Search?

At its core, search/searching is the process of finding a specific element or a group of elements within a collection of data. Search plays a crucial role in data structures by enabling quick access to required information from data sets that may vary widely in size and complexity.

• Searching involves scanning through a data structure–such as an array, list, or database–to locate an item that meets a specific criterion. This could be anything from finding a particular number in a list to retrieving a record from a database.
• Efficient searching is vital because it directly impacts the performance of software applications. Whether you're working on simple scripts or complex systems, the ability to search effectively can determine how fast your application responds and how well it scales.
• There are several methods for searching, each with its own use cases and performance characteristics. Linear search, which we are going to discuss in detail here, is one of the simplest forms and serves as a stepping stone to understanding more advanced search algorithms.

In the sections that follow, we’ll dive deep into the specifics of linear search in data structure–what it is, how it works, and where it’s best applied–providing you with a clear and actionable understanding of this fundamental algorithm.

What Is Linear Search In Data Structure?

Linear search, sometimes referred to as sequential search, is one of the simplest search methods used in computer science. This method works by iterating through each element in a data structure–such as an array or list–until the target element is found or the entire data structure has been examined.

Key Characteristics Of Linear Search

• Sequential Process: Linear search goes through the data structure one element at a time. It starts at the beginning and moves sequentially to the end, checking each element against the target value.
• Simplicity: Due to its straightforward approach, linear search is extremely easy to implement. This makes it an excellent choice for beginners learning about search algorithms and for scenarios where the dataset is relatively small or unsorted.
• Versatility: Unlike more complex algorithms, linear search does not require the data to be sorted. This flexibility means it can be applied to a variety of data structures without the need for pre-processing or additional constraints.

Practical Considerations When Using Linear Search In Data Structure

• Efficiency: While linear search is easy to understand and implement, its time complexity is O(n), meaning that in the worst case, it might need to inspect every element in the dataset. This makes it less efficient for large datasets compared to more advanced algorithms like binary search, which require sorted data.
• Memory Usage: One of the advantages of linear search is its minimal memory requirement–it typically only uses a constant amount of extra space (O(1)).

In summary, linear search is a fundamental technique that offers an excellent introduction to searching algorithms. Its ease of use and adaptability make it a valuable tool, especially when dealing with small or unsorted datasets where the overhead of more complex algorithms might not be justified.

What Is Linear Search Algorithm?

The Linear Search Algorithm is a method for finding a target value within a list by sequentially checking each element until the desired element is found or the list is exhausted. This algorithm is straightforward and intuitive, making it a great starting point for understanding more complex searching techniques. Here is a step-by-step breakdown of a linear search algorithm and its working:

1. Initialize the Search: Start from the first element of the data structure.
2. Compare Each Element: For each element in the data structure, compare it with the target value. If the element matches the target, record its index (or return it immediately). The search ends and returns the index.
3. Continue Until the End: If the current element does not match the target, move to the next element in the data structure.
4. Return the Result: If the target is found, return its position (index). If the search reaches the end of the list without finding the target, return a special value (e.g., -1) indicating that the target is not present.

Pseudocode For Linear Search Algorithm

FUNCTION linearSearch(array, target):
    FOR index FROM 0 TO LENGTH(array) - 1:
        IF array[index] == target:
            RETURN index   // Target found, return the index
    END FOR
    RETURN -1   // Target not found in the array

Explanation:

• Initialization: The algorithm begins at index 0 of the array.
• Iteration: It then iterates over each element in the array, comparing it with the target value.
• Conditional Check: If an element equals the target, the function immediately returns the index of that element.
• Completion: If no match is found after checking all elements, the function returns -1 to indicate the target does not exist within the array.

This step-by-step approach ensures that every element is examined, making the linear search a reliable, albeit not always the most efficient, method for finding an element in a list.

Working Of Linear Search Algorithm

To understand how the linear search algorithm works, let's break it down step by step with a visual representation. Consider an array of integers and a target value to be searched:

arr = [10, 25, 38, 45, 50, 67]
Target: 45

Step 1: Start from the first element

• Compare arr[0] (10) with 45.
• Since 10 ≠ 45, move to the next element.

Step 2: Compare the second element

• Compare arr[1] (25) with 45.
• Since 25 ≠ 45, move to the next element.

Step 3: Compare the third element

• Compare arr[2] (38) with 45.
• Since 38 ≠ 45, move to the next element.

Step 4: Compare the fourth element

• Compare arr[3] (45) with 45.
• Since 45 = 45, the target is found at index 3.
• The search stops, and the index 3 is recorded.

At this point, since the target element 45 is found at index 3, the function returns 3.

What Happens If the Target Is Not Found?

If the search reaches the end of the array without finding the target, it returns -1 to indicate that the element is not present. For example, when searching for 99 in the same array, the algorithm will check each element, but since 99 is not in the array, it will return -1.

This step-by-step approach ensures a clear understanding of how linear search operates.

Complexity Of Linear Search Algorithm In Data Structures

The efficiency of an algorithm is measured in terms of time complexity and space complexity. Since linear search is a simple sequential search method, its performance depends on the size of the dataset. Let’s analyze it in detail.

Time Complexity Of Linear Search

The time complexity of linear search is determined by the number of comparisons it makes to find the target element. The table below describes the time complexity for various cases:

As evident in the table above, the key takeaways for time complexity :

• Best Case (O(1)) → If the target element is at the very first position, the algorithm stops immediately, making it a constant-time operation.
• Average Case (O(n)) → On average, the target will be found somewhere around the middle of the dataset, requiring approximately n/2 comparisons (but still expressed as O(n) in Big-O notation).
• Worst Case (O(n)) → If the target is at the last position or not in the list at all, the algorithm must traverse the entire dataset, making n comparisons.

Space Complexity Of Linear Search

Linear search operates in place, meaning it does not require extra memory apart from a few variables.

• Space Complexity: O(1)
• Why? The algorithm only uses a few variables (such as loop counters and the target value) regardless of the input size, keeping space consumption constant.

Key Takeaways:

• Time Complexity: Linear in the worst case (O(n)), but can be very fast (O(1)) if the target is found early.
  Space Complexity: Constant (O(1)), making it memory-efficient.

Linear search is useful for small or unsorted datasets, but for larger data sets, more efficient algorithms like binary search (for sorted data) are preferred.

Implementations Of Linear Search Algorithm In Different Programming Languages

The linear search algorithm can be implemented in various programming languages. Below, we provide implementations in C, C++, Python, and Java, including the code, output, and explanation.

Linear Search Program In C

#include <stdio.h>

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

int main() {
int arr[] = {10, 25, 38, 45, 50, 67};
int target = 45;
int size = sizeof(arr) / sizeof(arr[0]);
int result = linearSearch(arr, size, target);

if (result != -1){
printf("Element found at index %d\n", result);
}else{
printf("Element not found\n");
}

return 0;
}

Output:

Element found at index 3

Code Explanation:

We begin by including the header file <stdio.h> for input/output operations. 

1. Function Definition: We define a function linearSearch(), which iterates through the array using a for loop.
2. Inside the loop, we have an if statement which checks if the current array element is equal to the target.
• If the target element is found, it returns the index.
• If the loop completes without finding the element, it returns -1.
3. Main Function Execution: We create an array, arr, containing 6 integer data type elements.
4. Then, we declare and initialize a variable target with the value 45.
5. Next, we calculate the size of the array using the sizeof the operator.
6. We then call the function linearSearch(), passing the array, size, and target as arguments. The outcome the function returns is stored in the result variable.
7. Result Handling: We use an if-else statement to check if the result is not -1 using the not equal to relational operator.
8. If the condition is true, we print the index value with a string message. If the condition i false, then the else block executes printing the string message– “Element not found”.

Linear Search Program In C++

#include <iostream>
using namespace std;

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

int main() {
int arr[] = {10, 25, 38, 45, 50, 67};
int target = 45;
int size = sizeof(arr) / sizeof(arr[0]);

int result = linearSearch(arr, size, target);

if (result != -1) {
cout << "Element found at index " << result << endl;
} else {
cout << "Element not found" << endl;
}

return 0;
}

Output:

Element found at index 3

Code Explanation:

1. Header File: We include <iostream> for input and output operations.
2. Function Definition: We define the C++ function linearSearch() that uses a for loop to iterate through the input array.
   • In every iteration, it uses an if-statement to check if the element matches the target.
   • If an element matches the target, the function returns its index.
   • If no match is found, -1 is returned.
3. Main Function Execution: We declare an integer array arr with six elements of integer data type.
   • We then declare a variable target and assign the integer value 45 to it.
   • The array size is computed using sizeof(arr) / sizeof(arr[0]).
   • We then call the function linearSearch() and store the returned value in the result.
4. Result Handling: We check the result using an if-else statement.
   • If result is not -1, we print the index where the element was found.
   • Otherwise, we print "Element not found".

Linear Search Program In Python

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

arr = [10, 25, 38, 45, 50, 67]
target = 45

result = linear_search(arr, target)

if result != -1:
    print(f"Element found at index {result}")
else:
  print("Element not found")

Output:

Element found at index 3

Code Explanation:

In the simple Python program example:

1. Function Definition: We define a Python function linear_search() that iterates through the list using a for loop with the range() function, i.e., range(len(arr)).
   • The range of the for loop iterations is set to the length of the array, calculated using the len() function.
   • In every iteration, we check if the current array element equals the target using the equality relational operator. 
   • If an element matches the target, the function returns the index.
   • If no match is found, the function returns -1.
2. Main Execution: We create a list, arr with six elements.
   • Then, we declare and initialize a variable target with the value 45.
   • Next, we call the linear_search() function and store the outcome in the variable result.
3. Result Handling: We use an if-else statement to check if the result is not -1.
   • If the result is not -1, we use the print() function to display the index where the element is found.
   • Otherwise, we print the string message– "Element not found".

Linear Search Program In Java

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

public static void main(String[] args) {
int arr[] = {10, 25, 38, 45, 50, 67};
int target = 45;

int result = linearSearch(arr, target);

if (result != -1) {
System.out.println("Element found at index " + result);
} else {
System.out.println("Element not found");
}
}

}

Output:

Element found at index 3

Code Explanation:

1. Class & Method Definition: We define a class LinearSearch containing a method linearSearch().
   • The method iterates through the array using a for loop control statement.
   • If an element matches the target, it returns the index; otherwise, it returns -1.
2. Main Execution: We declare an integer array arr with six elements.
   • The target variable is set to 45.
   • We call linearSearch() and store the result.
3. Result Handling:
   • If the result is not -1, the index is printed.
   • Otherwise, "Element not found" is displayed.

Real-World Applications Of Linear Search In Data Structure

Linear search is simple yet useful in scenarios where other complex search algorithms might be unnecessary or impractical. Here are some real-world applications:

• Finding a contact in a small, unsorted list– If you scroll through a phone contact list that isn’t sorted, you're essentially using linear search.
• Searching for an item in an inventory– Retail systems often scan small product lists sequentially when no indexing or sorting is available.
• Looking up a student's record in an attendance sheet– If student names are listed in order of entry rather than alphabetical order, a manual search follows the linear search principle.
• Detecting a specific keyword in a document– In text editors without advanced search indexing, checking word by word mimics linear search.
• Checking for a missing component in a toolkit– If you go through tools one by one to check if something is missing, you’re applying a linear search method.

Advantages & Disadvantages Of Linear Search

Linear search is straightforward but not always the most efficient method. Here’s a comparison of its pros and cons:

Best Practices For Using Linear Search Algorithm

To make the most of linear search, follow these best practices:

• Use it for small datasets– Linear search is efficient when dealing with small lists, where its simplicity outweighs the inefficiency of O(n) time complexity.
• Prefer it for unsorted data– When sorting isn’t feasible, linear search can be a good choice for quick lookups.
• Optimize with early termination– If you only need to check for existence (not count occurrences), return as soon as the element is found to avoid unnecessary iterations.
• Consider alternative searches for large datasets– For large collections, use binary search (if sorted) or hash-based searching (if frequent lookups are needed) to improve efficiency.
• Use linear search when dealing with linked lists– Since linked lists don’t allow direct access by index, linear search is often the simplest way to find elements.

Conclusion

Linear search is one of the simplest search algorithms, making it a great starting point for beginners in data structures and algorithms. While its O(n) time complexity makes it inefficient for large datasets, it remains useful for small, unsorted lists and certain real-world applications like searching in text documents or looking up records in an attendance sheet.

By understanding how linear search works, its advantages, limitations, and best use cases, you can make informed decisions on when to apply it or switch to more efficient search techniques like binary search or hash-based searching. Whether you're working with arrays, linked lists, or real-world data, knowing when and where to use linear search will strengthen your problem-solving skills.

Frequently Asked Questions

Q1. What are the scenarios where linear search is most effective?

Linear search is best for small, unsorted datasets where the overhead of sorting or using advanced search structures isn't justified. It's also useful for linked lists and when searching for the first occurrence of an element in an unsorted list.

Q2. How does linear search compare to other searching algorithms?

Linear search is simpler but slower than algorithms like binary search (O(log n)) or hash-based searches (O(1) in best cases). However, unlike binary search, it does not require sorted data.

Q3. What is the worst-case time complexity of linear search?

The worst-case time complexity is O(n), which happens when the element is at the end of the list or not present at all.

Q4. Can linear search be used for searching in linked lists?

Yes, linear search is commonly used in linked lists since they do not allow direct access to elements by index.

Q5. Is there any way to optimize linear search?

Optimizations include early termination (stopping the search once the element is found) and parallel searching (splitting the dataset into parts for faster searching). However, for large datasets, binary search or hash-based search techniques are usually better.

Q6. Can linear search be used in non-linear data structures?

Yes, linear search is not only for linear data structures. It can be applied to non-linear structures like linked lists, trees, and graphs, but its efficiency varies. It works well for linked lists since they require sequential access. In trees and graphs, more efficient traversal techniques like BFS (Breadth-First Search) and DFS (Depth-First Search) are usually preferred.

This compiles our discussion on linear search. Here are a few more blogs you must explore:

1. DSA Cheatsheet Unlocked: Roadmap, Boot Camp & Must-Know Resources
2. 55+ Data Structure Interview Questions For 2025 (Detailed Answers)
3. Time Complexity Of Algorithms: Types, Notations, Cases, and More
4. Difference Between Linear Search And Binary Search (+Code Example)
5. These Coding Algorithms Will Help You Crack Any Interview