Linear Search Algorithm

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.

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

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]

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

Advantages and Disadvantages

Applications of Linear Search

Comparison with Other Search Algorithms

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.

Next Steps

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

Related Tutorials