Your Progress

15/30 completed

50% complete. Continue learning to master DSA!

Linear Search Algorithm

Linear search is the simplest searching algorithm that checks each element in a collection one by one until the target element is found or the collection is exhausted.

Key Takeaways

  • Linear search examines each element sequentially until a match is found
  • Time complexity is O(n) in the worst case, making it inefficient for large datasets
  • Space complexity is O(1) as it requires constant extra space
  • Works on both sorted and unsorted collections, unlike binary search
  • Easy to implement and understand, but typically outperformed by more efficient algorithms

What is Linear Search?

Linear search (also called sequential search) is a method for finding an element within a list by checking each element in sequence until a match is found or the entire list has been searched. It's the most basic searching algorithm and works on both sorted and unsorted data.

How Linear Search Works

  1. Start from the first element (index 0) of the array or list
  2. Compare the current element with the target element
  3. If the elements match, return the current index
  4. If they don't match, move to the next element
  5. Repeat steps 2-4 until the element is found or the end of the array is reached
  6. If the end of the array is reached without finding the element, return -1 or an appropriate value to indicate the element is not present

Visual Example

Let's search for the value 7 in the following array:

Array: [3, 1, 4, 1, 5, 9, 2, 6, 5]
Target: 7

Step 1: Check index 0: 3 ≠ 7, continue
Step 2: Check index 1: 1 ≠ 7, continue
Step 3: Check index 2: 4 ≠ 7, continue
Step 4: Check index 3: 1 ≠ 7, continue
Step 5: Check index 4: 5 ≠ 7, continue
Step 6: Check index 5: 9 ≠ 7, continue
Step 7: Check index 6: 2 ≠ 7, continue
Step 8: Check index 7: 6 ≠ 7, continue
Step 9: Check index 8: 5 ≠ 7, continue

After checking all elements, 7 is not found in the array.
Return -1 (or similar indicator)

Implementing Linear Search

Here are implementations of linear search in various programming languages:

1function linearSearch(arr, target) {
2 // Iterate through each element in the array
3 for (let i = 0; i < arr.length; i++) {
4 // If the current element matches the target
5 if (arr[i] === target) {
6 return i; // Return the current index
7 }
8 }
9
10 // If the element is not found
11 return -1;
12}
13
14// Example usage
15const array = [3, 1, 4, 1, 5, 9, 2, 6, 5];
16console.log(linearSearch(array, 9)); // Output: 5
17console.log(linearSearch(array, 7)); // Output: -1

Variations of Linear Search

1. Early Termination

This is the standard implementation where the search stops as soon as the target element is found.

2. Find All Occurrences

This variation finds all occurrences of the target element rather than stopping after the first match.

1function findAllOccurrences(arr, target) {
2 const indices = [];
3
4 // Iterate through each element in the array
5 for (let i = 0; i < arr.length; i++) {
6 // If the current element matches the target
7 if (arr[i] === target) {
8 indices.push(i); // Add the index to our result array
9 }
10 }
11
12 return indices;
13}
14
15// Example usage
16const array = [1, 2, 3, 1, 4, 1, 5];
17console.log(findAllOccurrences(array, 1)); // Output: [0, 3, 5]

3. Sentinel Linear Search

Sentinel linear search is an optimization that eliminates the need to check if the current index is within bounds in each iteration. This is done by placing the target element at the end of the array as a sentinel.

1function sentinelLinearSearch(arr, target) {
2 const n = arr.length;
3
4 // Save the last element
5 const last = arr[n - 1];
6
7 // Replace last element with the target
8 arr[n - 1] = target;
9
10 let i = 0;
11 // Keep going until we find the target
12 // No need to check array bounds
13 while (arr[i] !== target) {
14 i++;
15 }
16
17 // Restore the last element
18 arr[n - 1] = last;
19
20 // If we found the target before the last element
21 // or if the last element is the target
22 if (i < n - 1 || target === last) {
23 return i;
24 }
25
26 // Target not found
27 return -1;
28}
29
30// Example usage
31const array = [3, 1, 4, 1, 5, 9, 2, 6, 5];
32console.log(sentinelLinearSearch(array, 9)); // Output: 5
33console.log(sentinelLinearSearch(array, 7)); // Output: -1

Time and Space Complexity

Time Complexity

  • Best Case: O(1) - The target element is the first element in the array
  • Average Case: O(n/2) ≈ O(n) - On average, we'll need to check half the elements
  • Worst Case: O(n) - The target element is the last element in the array or not present

Space Complexity

  • Space Complexity: O(1) - Linear search uses a constant amount of extra space regardless of input size

Advantages and Disadvantages

Advantages

  • Simple to implement: The algorithm is straightforward and easy to understand
  • Works on unsorted data: No pre-sorting required, unlike binary search
  • No extra memory: Uses constant space regardless of input size
  • Works on any searchable data structure: Can be applied to arrays, linked lists, etc.
  • Preferable for small datasets: Simple and effective for small collections

Disadvantages

  • Inefficient for large datasets: O(n) time complexity doesn't scale well
  • Slower than specialized algorithms: For sorted data, binary search is much faster (O(log n))
  • Sequential access: Cannot skip elements, must check each one in order
  • Not cache-friendly: May cause more cache misses than algorithms with better locality

Applications of Linear Search

Practical Use Cases

  • Small datasets: When working with small amounts of data, linear search may be more practical than implementing more complex algorithms
  • Unsorted data: When the data is not sorted and a one-time search is needed
  • Searching in linked lists: Where random access is not available, making binary search impractical
  • Searching rare items: When the target element is known to be near the beginning of the list
  • Searching for complex criteria: When searching based on a condition rather than an exact match

Real-World Examples

  • Finding an element in a small array or list where the overhead of sorting and more complex algorithms isn't justified
  • Searching for a specific record in a small database when indexes aren't available
  • Finding a specific character in a string (many string methods use linear search internally)
  • Checking if an element exists in an unsorted collection
  • Finding the minimum or maximum value in an unsorted array

Comparison with Other Search Algorithms

AlgorithmTime ComplexitySpace ComplexityData StructureRequires Sorting
Linear SearchO(n)O(1)AnyNo
Binary SearchO(log n)O(1)Array/Random AccessYes
Hash Table LookupO(1) averageO(n)Hash TableNo
Interpolation SearchO(log log n) averageO(1)Array/Random AccessYes

While linear search is the simplest to implement, it's generally outperformed by other algorithms for larger datasets. However, for small datasets or when the data is unsorted and will only be searched once, linear search might be the most practical choice.

Conclusion

Linear search is the most straightforward searching algorithm and serves as a foundation for understanding more complex search techniques. Despite its simplicity and O(n) time complexity, it remains useful in specific scenarios, particularly for small datasets and unsorted collections.

When to Use Linear Search

  • When working with small datasets where the overhead of more complex algorithms isn't justified
  • When the data is unsorted and will only be searched once (making sorting + binary search inefficient)
  • When implementing search functionality in data structures that don't support random access (like linked lists)
  • When searching for multiple criteria that can't be easily indexed or sorted

Next Steps

To continue your learning about search algorithms, explore these related topics:

Related Tutorials

Related Tutorials

Binary Search

Learn a more efficient search algorithm for sorted arrays.

Learn more

Arrays

Understand the fundamental data structure used with linear search.

Learn more

Searching Algorithms

Explore other algorithms for finding elements in data structures.

Learn more