Linear Search

What is a Linear Search?

When we think about searching algorithms, we often expect them to be complicated. After all, JavaScript provides native methods like filter and indexOf that handle searching for us. However, understanding how these methods work under the hood is crucial.

Spoiler alert: they often use linear search. Linear search is one of the simplest algorithms. While it may not be the most efficient, especially for large datasets, it works unconditionally, no need for the array to be sorted.

Let's consider an example: checking if a username is already taken. Suppose we have an array storing all the usernames that are already taken. We can simply check if the provided value is strictly equal to any value in the array.

function checkUsernameAvailable(usernames, value) {
  for (let username of usernames) {
    if (username === value) {
      return true;
    }
  }
  return false;
}

That's it, the function simply loops over every element until it finds the value. If it finds the value, it returns true otherwise, it returns false.

Alternatively, we could return the index of the found value, similar to how indexOf works:

function findIndex(usernames, value) {
  for (let i = 0; i < usernames.length; i++) {
    if (usernames[i] === value) {
      return i;
    }
  }
  return -1;
}

As simple as it seems, it's often unnecessary to overcomplicate things, especially when dealing with small datasets.

Performance considerations

Performance-wise, note that linear search has a Big O notation of O(N), meaning its efficiency decreases proportionally to the input size. If you have a large dataset, it might be wise to consider other search algorithms, such as binary search (which requires a sorted array) or more advanced data structures like hash tables.

When to Use Linear Search

• Small Datasets: For small arrays, the simplicity and ease of implementation make linear search a good choice.
• Unsorted Data: Linear search does not require the data to be sorted, making it versatile for various types of datasets.
• Simplicity: When the overhead of more complex algorithms is not justified, linear search is straightforward and easy to understand.

Conclusion

Linear search is a fundamental algorithm that every developer should understand. While it may not be the most efficient for large datasets, its simplicity and versatility make it a valuable tool in your programming toolkit.

Happy coding ! 👨🏻‍💻