JavaScript Linear Search

Posted on: 2017-06-12

Linear search is a basic search that is slow. Slow in the magnitude of having an asymptotic analysis of a BigO of O(n). This is the worse case is that the item is at the last position which require to traverse the whole array. Linear search moves one to one and check the value. It has the advantage of not needing to have an input sorted.

var arrayToSearch = [7, 23, 4, 23, 87, 2, 6, 3, 213, 43, 34, 1, 76, 43];

console.log("Found at position :" + linearSearch(arrayToSearch, 34));

function linearSearch(arrayToSearch, valueToSearch) {
  var length = arrayToSearch.length;
  for (var i = 0; i < length; i++) {
    if (arrayToSearch[i] === valueToSearch) {
      return i;
    }
  }
  return -1;
}

Here is a naive implementation where -1 is returned in the case of no element found. As you can see, the function is under the invocation of the function. This is possible because of JavaScript's hoisting mechanism that move function declaration at the beginning of the scope (not function expression).

A recursive solution is also possible :

console.log("Found at position :" + linearSearch(arrayToSearch, 34, 0));
function linearSearch(arrayToSearch, valueToSearch, index) {
  if (arrayToSearch.length === 0) {
    return -1;
  }
  if (arrayToSearch[0] === valueToSearch) {
    return index;
  }
  return linearSearch(arrayToSearch.slice(1), valueToSearch, index + 1);
}

The idea is to recursively remove the first element of the array and pass it down to the method again and again until the array is empty or the value is found.