JavaScript Algorithms: Linear Search

Linear search, also called sequential or simple, is the most basic search algorithm. Given a data structure, for example an array, we search for an item by looking at all the elements, until we find it.

Its implementation is very simple:

const linearSearch = (list, item) => {
  for (const [i, element] of list.entries()) {
    if (element === item) {
      return i
    }
  }
}

The entries() method gives us both the index and the element at each step of the loop. When the element matches, we return its index. Example:

linearSearch(['a', 'b', 'c', 'd'], 'd') //3 (index start at 0)

What if the item is not there?

Our function ends without hitting a return, so it returns undefined.

That works, but the convention in JavaScript is to return -1 when a search fails. That’s what indexOf() does. We can add that as the last line:

const linearSearch = (list, item) => {
  for (const [i, element] of list.entries()) {
    if (element === item) {
      return i
    }
  }
  return -1
}

linearSearch(['a', 'b'], 'z') //-1

You already use it every day

The array methods indexOf(), includes(), find() and findIndex() all do a linear scan internally. Writing the algorithm by hand is mostly useful to understand what those methods cost you when the array grows.

Complexity

If we look for ‘a’, the algorithm will only look at the first element and return, so it’s very fast.

But if we look for the last element, the algorithm needs to loop through all the array. To calculate the Big O value we always look at the worst-case scenario.

So the algorithm complexity is O(n). Double the elements, double the work.

Linear search is fine for small arrays, and it’s your only option when the data is unsorted. Binary search is much faster, but it only works on sorted data.

Be careful with objects

The === comparison checks object references, not their content. Two objects that look identical are not equal:

const users = [{ name: 'Ada' }, { name: 'Grace' }]

linearSearch(users, { name: 'Ada' }) //-1

The object literal we pass is a brand new object, so it never matches. To search an array of objects, compare a property instead:

users.findIndex((user) => user.name === 'Ada') //0