Linear Search Algorithm Tutorial

Introduction

The linear search algorithm is a simple and straightforward searching algorithm used to find a specific element within a list or array. It works by iterating through each element of the list sequentially until the target element is found or the end of the list is reached.

How Linear Search Works

1. Start at the beginning: The search begins by examining the first element in the list.
2. Compare and check: The algorithm compares the current element with the target element.
   • If they match, the search is successful, and the position of the element is returned.
   • If they don't match, the algorithm moves on to the next element in the list.
3. Repeat: Steps 1 and 2 are repeated until either the target element is found or the end of the list is reached.
4. Return result: If the target element is found, its position (index) is returned. If the element is not found, a specific value like -1 or null is returned to indicate that the element was not present in the list.

Example

Let's consider the following list of numbers:

[5, 12, 3, 7, 1, 9]

We want to search for the number 7 using a linear search.

1. We start by comparing the first element (5) with 7. They don't match.
2. We move to the next element (12) and compare it with 7. They don't match.
3. We continue comparing until we reach the element 7.
4. The algorithm stops when it finds 7 and returns its position (index), which is 3.

Code Implementation

function linearSearch(list, target) {
  for (let i = 0; i < list.length; i++) {
    if (list[i] === target) {
      return i;
    }
  }
  return -1;
}

Time Complexity

The time complexity of linear search is O(n), where n is the number of elements in the list. This means that the time it takes to search the list grows linearly with the number of elements. In the worst case, the algorithm has to check every element in the list before finding the target element or determining that it's not present.

Advantages

• Easy to implement: The linear search algorithm is very simple to understand and implement.
• Works on any data structure: It can be used to search any kind of list or array, regardless of whether it's sorted or unsorted.

Disadvantages

• Inefficient for large lists: For large lists, linear search can be very slow, especially in the worst case.
• Not suitable for sorted data: For sorted lists, other more efficient algorithms like binary search are preferred.

Conclusion

The linear search algorithm is a basic but useful searching technique that can be applied to any list or array. While it is simple to implement, it's important to consider its time complexity and limitations, especially for large datasets. For sorted lists, more efficient algorithms like binary search should be considered.