Linear Search

Welcome to Linear Search, the most straightforward searching algorithm. As its name suggests, it involves a linear scan through a collection of elements, one by one, until the target element is found or the end of the collection is reached.

1. The Core Idea: A Simple Scan

The strategy of linear search is simple and intuitive. It starts at the beginning of a list (like an array) and compares each element with the target value. If a match is found, the search is successful and the position of the element is returned. If the entire list is scanned and no match is found, the search is unsuccessful.

This algorithm can be used on any type of list, whether it is sorted or unsorted.

2. The Algorithm Step-by-Step

Start: Begin at the first element of the collection (index 0).
Compare: Compare the current element with the target value.
Match Found: If the current element is equal to the target, return the current index.
Continue: If the current element is not equal to the target, move to the next element in the collection.
End of List: If the end of the collection is reached without finding the target, the search concludes, and a special value (like -1) is returned to indicate that the target was not found.

3. Implementation

function linearSearch(array, target) {
  // Iterate through each element of the array
  for (let i = 0; i < array.length; i++) {
    // If the current element matches the target, return its index
    if (array[i] === target) {
      return i;
    }
  }

  // If the loop completes without finding the target, return -1
  return -1;
}

4. Complexity Analysis

Time Complexity: O(N), where N is the number of elements in the collection. In the worst-case scenario, we have to scan the entire list.
Space Complexity: O(1), as we only need a constant amount of extra space to store the loop variable.

5. When to Use Linear Search

While linear search is not the most efficient searching algorithm, it is a good choice in several situations:

When the collection is small.
When the collection is unsorted.
When you need a simple implementation and performance is not a critical concern.

Key Takeaway: Linear search is a fundamental, easy-to-implement algorithm that sequentially scans a collection to find a target value. Its O(N) time complexity makes it suitable for small or unsorted datasets.